<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width,initial-scale=1"><title>数据结构与算法实验指导书 | 小谭的部落阁</title><meta name="keywords" content="工具,论文,公式,latex"><meta name="author" content="谭自财"><meta name="copyright" content="谭自财"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="《数据结构》上机实验内容和要求通过上机实验加深对课程内容的理解，提高程序设计、开发及调试能力。本实验指导书适用于16学时《数据结构法》实验课，实验项目具体内容如下： layout: pagestitle: 数据结构与算法实验指导书author: 谭自财date: 2021-03-21 07:21:35categories: 数据结构与算法tags:  数据结构 算法 C语言 实验  实验报告要求">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法实验指导书">
<meta property="og:url" content="https://tanzicai.gitee.io/2021/03/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%AE%9E%E9%AA%8C%E6%8C%87%E5%AF%BC%E4%B9%A6/index.html">
<meta property="og:site_name" content="小谭的部落阁">
<meta property="og:description" content="《数据结构》上机实验内容和要求通过上机实验加深对课程内容的理解，提高程序设计、开发及调试能力。本实验指导书适用于16学时《数据结构法》实验课，实验项目具体内容如下： layout: pagestitle: 数据结构与算法实验指导书author: 谭自财date: 2021-03-21 07:21:35categories: 数据结构与算法tags:  数据结构 算法 C语言 实验  实验报告要求">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://tanzicai.gitee.io/img/survivors_v02_5120x2880.png">
<meta property="article:published_time" content="2021-03-20T23:21:35.000Z">
<meta property="article:modified_time" content="2021-07-11T09:06:40.000Z">
<meta property="article:author" content="谭自财">
<meta property="article:tag" content="工具">
<meta property="article:tag" content="论文">
<meta property="article:tag" content="公式">
<meta property="article:tag" content="latex">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://tanzicai.gitee.io/img/survivors_v02_5120x2880.png"><link rel="shortcut icon" href="/img/favicon.png"><link rel="canonical" href="https://tanzicai.gitee.io/2021/03/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%AE%9E%E9%AA%8C%E6%8C%87%E5%AF%BC%E4%B9%A6/"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><meta/><link rel="stylesheet" href="/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/',
  algolia: undefined,
  localSearch: undefined,
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"简"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":false},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: false,
    post: false
  },
  runtime: '天',
  date_suffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: undefined,
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    jQuery: 'https://cdn.jsdelivr.net/npm/jquery@latest/dist/jquery.min.js',
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/js/jquery.justifiedGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/justifiedGallery/dist/css/justifiedGallery.min.css'
    },
    fancybox: {
      js: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.js',
      css: 'https://cdn.jsdelivr.net/npm/@fancyapps/fancybox@latest/dist/jquery.fancybox.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isanchor: false
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '数据结构与算法实验指导书',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2021-07-11 17:06:40'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const fontSizeVal = saveToLocal.get('global-font-size')
    if (fontSizeVal !== undefined) {
      document.documentElement.style.setProperty('--global-font-size', fontSizeVal + 'px')
    }
    })(window)</script><meta name="generator" content="Hexo 5.4.0"><link rel="alternate" href="/atom.xml" title="小谭的部落阁" type="application/atom+xml">
</head><body><div id="loading-box"><div class="loading-left-bg"></div><div class="loading-right-bg"></div><div class="spinner-box"><div class="configure-border-1"><div class="configure-core"></div></div><div class="configure-border-2"><div class="configure-core"></div></div><div class="loading-word">加载中...</div></div></div><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="author-avatar"><img class="avatar-img" src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210609205810.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="site-data"><div class="data-item is-center"><div class="data-item-link"><a href="/archives/"><div class="headline">文章</div><div class="length-num">35</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/tags/"><div class="headline">标签</div><div class="length-num">50</div></a></div></div><div class="data-item is-center"><div class="data-item-link"><a href="/categories/"><div class="headline">分类</div><div class="length-num">12</div></a></div></div></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标籤</span></a></div><div class="menus_item"><a class="site-page" href="/category/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/fridends/"><i class="fa-fw fa fa-heartbeat"></i><span> 朋友圈</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/download/"><i class="fa-fw fas fa--cloud-download"></i><span> 下载</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-hear"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('/img/survivors_v02_5120x2880.png')"><nav id="nav"><span id="blog_name"><a id="site-name" href="/">小谭的部落阁</a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/tags/"><i class="fa-fw fas fa-tags"></i><span> 标籤</span></a></div><div class="menus_item"><a class="site-page" href="/category/"><i class="fa-fw fas fa-folder-open"></i><span> 分类</span></a></div><div class="menus_item"><a class="site-page" href="/fridends/"><i class="fa-fw fa fa-heartbeat"></i><span> 朋友圈</span></a></div><div class="menus_item"><a class="site-page" href="/link/"><i class="fa-fw fas fa-link"></i><span> 友链</span></a></div><div class="menus_item"><a class="site-page" href="/download/"><i class="fa-fw fas fa--cloud-download"></i><span> 下载</span></a></div><div class="menus_item"><a class="site-page" href="/about/"><i class="fa-fw fas fa-hear"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">数据结构与算法实验指导书</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-03-20T23:21:35.000Z" title="发表于 2021-03-21 07:21:35">2021-03-21</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2021-07-11T09:06:40.000Z" title="更新于 2021-07-11 17:06:40">2021-07-11</time></span><span class="post-meta-categories"><span class="post-meta-separator">|</span><i class="fas fa-inbox fa-fw post-meta-icon"></i><a class="post-meta-categories" href="/categories/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95/">数据结构与算法</a></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="数据结构与算法实验指导书"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h2 id="《数据结构》上机实验内容和要求"><a href="#《数据结构》上机实验内容和要求" class="headerlink" title="《数据结构》上机实验内容和要求"></a>《数据结构》上机实验内容和要求</h2><p>通过上机实验加深对课程内容的理解，提高程序设计、开发及调试能力。本实验指导书适用于16学时《数据结构法》实验课，实验项目具体内容如下：</p>
<p>layout: pages<br>title: 数据结构与算法实验指导书<br>author: 谭自财<br>date: 2021-03-21 07:21:35<br>categories: 数据结构与算法<br>tags:</p>
<ul>
<li>数据结构</li>
<li>算法</li>
<li>C语言</li>
<li>实验</li>
</ul>
<h2 id="实验报告要求"><a href="#实验报告要求" class="headerlink" title="实验报告要求"></a>实验报告要求</h2><blockquote>
<p>请按照评分标准和报告模板要求，提交实验报告电子版文件。</p>
</blockquote>
<h1 id="👦实验一、顺序表的实现及应用"><a href="#👦实验一、顺序表的实现及应用" class="headerlink" title="👦实验一、顺序表的实现及应用"></a>👦<strong>实验一、顺序表的实现及应用</strong></h1><h2 id="一、实验目的"><a href="#一、实验目的" class="headerlink" title="一、实验目的"></a><strong>一、实验目的</strong></h2><p>了解和掌握线性表的顺序存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。</p>
<h2 id="二、实验要求"><a href="#二、实验要求" class="headerlink" title="二、实验要求"></a><strong>二、实验要求</strong></h2><p>给定一段程序代码，程序代码所完成的功能为：</p>
<p>（1）建立一个线性表；</p>
<p>（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；</p>
<p>（3）删除数据元素5；</p>
<p>（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用顺序表。</p>
<p>程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，修改后上机调试得到正确的运行结果。</p>
<h2 id="三、程序代码"><a href="#三、程序代码" class="headerlink" title="三、程序代码"></a><strong>三、程序代码</strong></h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">6</span> <span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&quot;stdlib.h&quot;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MaxSize  100</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> DataType;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    DataType <span class="built_in">list</span>[MaxSize];</span><br><span class="line">    <span class="keyword">int</span> size;</span><br><span class="line">&#125; SeqList;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListInitiate</span><span class="params">(SeqList *L)</span><span class="comment">/*初始化顺序表L*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    L-&gt;size = <span class="number">0</span>;<span class="comment">/*定义初始数据元素个数*/</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListLength</span><span class="params">(SeqList L)</span><span class="comment">/*返回顺序表L的当前数据元素个数*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> L.size;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListInsert</span><span class="params">(SeqList *L, <span class="keyword">int</span> i, DataType x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*在顺序表L的位置i（0 ≤ i ≤ size）前插入数据元素值x*/</span></span></span><br><span class="line"><span class="function"><span class="comment">/*插入成功返回1，插入失败返回0*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> j;</span><br><span class="line">    <span class="keyword">if</span>(L-&gt;size &gt;= MaxSize)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;顺序表已满无法插入! \\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(i &lt; <span class="number">0</span> || i &gt; L-&gt;size )</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;参数i不合法! \\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123; <span class="comment">//此段程序有一处错误</span></span><br><span class="line">        <span class="keyword">for</span>(j = L-&gt;size; j &gt;= i; j--) L-&gt;<span class="built_in">list</span>[j+<span class="number">1</span>] = L-&gt;<span class="built_in">list</span>[j];<span class="comment">/*为插入做准备*/</span></span><br><span class="line">        L-&gt;<span class="built_in">list</span>[i] = x;<span class="comment">/*插入*/</span></span><br><span class="line">        L-&gt;size ++;<span class="comment">/*元素个数加1*/</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListDelete</span><span class="params">(SeqList *L, <span class="keyword">int</span> i, DataType *x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*删除顺序表L中位置i（0 ≤ i ≤ size - 1）的数据元素值并存放到参数x中*/</span></span></span><br><span class="line"><span class="function"><span class="comment">/*删除成功返回1，删除失败返回0*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> j;</span><br><span class="line">    <span class="keyword">if</span>(L-&gt;size &lt;= <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;顺序表已空无数据元素可删! \\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> <span class="keyword">if</span>(i &lt; <span class="number">0</span> || i &gt; L-&gt;size<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;参数i不合法&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;<span class="comment">//此段程序有一处错误</span></span><br><span class="line"></span><br><span class="line">        *x = L-&gt;<span class="built_in">list</span>[i];<span class="comment">/*保存删除的元素到参数x中*/</span></span><br><span class="line">        <span class="keyword">for</span>(j = i +<span class="number">1</span>; j &lt;= L-&gt;size<span class="number">-1</span>; j++) L-&gt;<span class="built_in">list</span>[j<span class="number">-1</span>] = L-&gt;<span class="built_in">list</span>[j];<span class="comment">/*依次前移*/</span></span><br><span class="line">        L-&gt;size--;<span class="comment">/*数据元素个数减1*/</span></span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListGet</span><span class="params">(SeqList L, <span class="keyword">int</span> i, DataType *x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*取顺序表L中第i个数据元素的值存于x中，成功则返回1，失败返回0*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(i &lt; <span class="number">0</span> || i &gt; L.size<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;参数i不合法! \\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        *x = L.<span class="built_in">list</span>[i];</span><br><span class="line">        <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListMerge</span><span class="params">(SeqList L1,SeqList L2,SeqList *L3)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ai=<span class="number">0</span>,bi=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,j=<span class="number">0</span>,k=<span class="number">0</span>;</span><br><span class="line">    ListInitiate(L3);</span><br><span class="line">    <span class="keyword">while</span> (i &lt;= ListLength(L1)<span class="number">-1</span> &amp;&amp; j &lt;= ListLength(L2)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L1,i,&amp;ai);</span><br><span class="line">        ListGet(L2,j,&amp;bi);</span><br><span class="line">        <span class="keyword">if</span> (ai&lt;=bi)</span><br><span class="line">        &#123;</span><br><span class="line">            ListInsert(L3,k++,ai);</span><br><span class="line">            ++i;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            ListInsert(L3, k++, bi);</span><br><span class="line">            ++j;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=ListLength(L1)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L1,i++,&amp;ai);</span><br><span class="line">        ListInsert(L3,++k,ai);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (j&lt;=ListLength(L2)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L2,j++,&amp;bi);</span><br><span class="line">        ListInsert(L3,k++,bi);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;   SeqList myList;</span><br><span class="line">    SeqList <span class="built_in">list</span>;</span><br><span class="line">    SeqList listAll;</span><br><span class="line">    <span class="keyword">int</span> i , x;</span><br><span class="line">    ListInitiate(&amp;myList);</span><br><span class="line">    ListInitiate(&amp;<span class="built_in">list</span>);</span><br><span class="line">    ListInitiate(&amp;listAll);</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; <span class="number">10</span>; i++)</span><br><span class="line">        ListInsert(&amp;myList, i, i+<span class="number">1</span>);</span><br><span class="line">    ListDelete(&amp;myList, <span class="number">4</span>, &amp;x);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; <span class="number">10</span>; ++j) &#123;</span><br><span class="line">        ListInsert(&amp;<span class="built_in">list</span>,j,j+<span class="number">21</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    ListMerge(myList,<span class="built_in">list</span>,&amp;listAll);</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; ListLength(myList); i++)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(myList,i,&amp;x); <span class="comment">//此段程序有一处错误</span></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\\n&quot;</span>, x);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\\n&quot;</span>);</span><br><span class="line">    <span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; ListLength(<span class="built_in">list</span>); i++)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(<span class="built_in">list</span>,i,&amp;x); <span class="comment">//此段程序有一处错误</span></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\\n&quot;</span>, x);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; ListLength(listAll); i++) &#123;</span><br><span class="line">        ListGet(listAll,i,&amp;x);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d\\n&quot;</span>,x);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="合并函数-WriteByLiyihan"><a href="#合并函数-WriteByLiyihan" class="headerlink" title="合并函数_WriteByLiyihan"></a>合并函数_WriteByLiyihan</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListMerge</span><span class="params">(SeqList L1,SeqList L2,SeqList *L3)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> ai=<span class="number">0</span>,bi=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,j=<span class="number">0</span>,k=<span class="number">0</span>;</span><br><span class="line">    ListInitiate(L3);</span><br><span class="line">    <span class="keyword">while</span> (i &lt;= ListLength(L1)<span class="number">-1</span> &amp;&amp; j &lt;= ListLength(L2)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L1,i,&amp;ai);</span><br><span class="line">        ListGet(L2,j,&amp;bi);</span><br><span class="line">        <span class="keyword">if</span> (ai&lt;=bi)</span><br><span class="line">        &#123;</span><br><span class="line">            ListInsert(L3,k++,ai);</span><br><span class="line">            ++i;</span><br><span class="line"></span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;</span><br><span class="line">            ListInsert(L3, k++, bi);</span><br><span class="line">            ++j;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=ListLength(L1)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L1,i++,&amp;ai);</span><br><span class="line">        ListInsert(L3,++k,ai);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (j&lt;=ListLength(L2)<span class="number">-1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        ListGet(L2,j++,&amp;bi);</span><br><span class="line">        ListInsert(L3,k++,bi);</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="四、实验任务"><a href="#四、实验任务" class="headerlink" title="四、实验任务"></a><strong>四、实验任务</strong></h2><p>1.改正上述程序中的错误。</p>
<p>2.编写合并函数，将两个有序线性表合并为一个有序表并在主函数中加以测试。</p>
<p>3.完成实验报告的撰写。</p>
<h1 id="实验二-链表的实现及应用"><a href="#实验二-链表的实现及应用" class="headerlink" title="实验二 链表的实现及应用"></a><strong>实验二 链表的实现及应用</strong></h1><h2 id="一、实验目的-1"><a href="#一、实验目的-1" class="headerlink" title="一、实验目的"></a><strong>一、实验目的</strong></h2><p>了解和掌握线性表的链式存储结构；掌握用C语言上机调试线性表的基本方法；掌握线性表的基本操作：插入、删除、查找以及线性表合并等运算在顺序存储结构和链接存储结构上的运算，以及对相应算法的性能分析。</p>
<h2 id="二、实验要求-1"><a href="#二、实验要求-1" class="headerlink" title="二、实验要求"></a><strong>二、实验要求</strong></h2><p>给定一段程序代码，程序代码所完成的功能为：</p>
<p>（1）建立一个线性表；</p>
<p>（2）依次输入数据元素1,2,3,4,5,6,7,8,9,10；</p>
<p>（3）删除数据元素5；</p>
<p>（4）依次显示当前线性表中的数据元素。假设该线性表的数据元素个数在最坏情况下不会超过100个，要求使用单链表。</p>
<p>程序中有3处错误的地方，有标识，属于逻辑错误，对照书中的代码仔细分析后，要求同学们修改错误的代码，上机调试并得到正确的运行结果。</p>
<h2 id="三、程序代码："><a href="#三、程序代码：" class="headerlink" title="三、程序代码："></a><strong>三、程序代码：</strong></h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span><span class="comment">/*该文件包含printf()等函数*/</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span><span class="comment">/*该文件包含exit()等函数*/</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;malloc.h&gt;</span><span class="comment">/*该文件包含malloc()等函数*/</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">int</span> DataType;<span class="comment">/*定义DataType为int*/</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">	DataType data;</span><br><span class="line">	<span class="class"><span class="keyword">struct</span> <span class="title">Node</span> *<span class="title">next</span>;</span></span><br><span class="line">&#125; SLNode;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">ListInitiate</span><span class="params">(SLNode **head)</span><span class="comment">/*初始化*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"><span class="comment">/*如果有内存空间，申请头结点空间并使头指针head指向头结点*/</span></span><br><span class="line">	<span class="keyword">if</span>((*head = (SLNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(SLNode))) == <span class="literal">NULL</span>) <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">	(*head)-&gt;next = <span class="literal">NULL</span>;<span class="comment">/*置链尾标记NULL */</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListLength</span><span class="params">(SLNode *head)</span>        <span class="comment">/* 单链表的长度*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *p = head;<span class="comment">/*p指向首元结点*/</span></span><br><span class="line">	<span class="keyword">int</span> size = <span class="number">0</span>;<span class="comment">/*size初始为0*/</span></span><br><span class="line">	<span class="keyword">while</span>(p-&gt;next != <span class="literal">NULL</span>)<span class="comment">/*循环计数*/</span></span><br><span class="line">	&#123;</span><br><span class="line">		p = p-&gt;next;</span><br><span class="line">		size ++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">return</span> size;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListInsert</span><span class="params">(SLNode *head, <span class="keyword">int</span> i, DataType x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*在带头结点的单链表head的数据元素ai（0 ≤ i ≤ size）结点前*/</span></span></span><br><span class="line"><span class="function"><span class="comment">/*插入一个存放数据元素x的结点*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *p, *q;</span><br><span class="line">	<span class="keyword">int</span> j;</span><br><span class="line">	p = head; <span class="comment">/*p指向首元结点*/</span></span><br><span class="line">	j = <span class="number">-1</span>;<span class="comment">/*j初始为-1*/</span></span><br><span class="line">	<span class="keyword">while</span>(p-&gt;next != <span class="literal">NULL</span> &amp;&amp; j &lt; i - <span class="number">1</span>) </span><br><span class="line"><span class="comment">/*最终让指针p指向数据元素ai-1结点*/</span></span><br><span class="line">	&#123;</span><br><span class="line">		p = p-&gt;next;</span><br><span class="line">		j++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(j != i - <span class="number">1</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;插入位置参数错！&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line"><span class="comment">/*生成新结点由指针q指示*/</span></span><br><span class="line">	<span class="keyword">if</span>((q = (SLNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(SLNode))) == <span class="literal">NULL</span>) <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">		q-&gt;data = x; </span><br><span class="line"><span class="comment">//此段程序有一处错误</span></span><br><span class="line">	q-&gt;next = p-&gt;next;<span class="comment">/*给指针q-&gt;next赋值*/</span></span><br><span class="line">	p-&gt;next = q;<span class="comment">/*给指针p-&gt;next重新赋值*/</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListDelete</span><span class="params">(SLNode *head, <span class="keyword">int</span> i, DataType *x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*删除带头结点的单链表head的数据元素ai（0 ≤ i ≤ size - 1）结点*/</span></span></span><br><span class="line"><span class="function"><span class="comment">/*删除结点的数据元素域值由x带回。删除成功时返回1；失败返回0*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *p, *s;</span><br><span class="line">	<span class="keyword">int</span> j;</span><br><span class="line">	p = head; <span class="comment">/*p指向首元结点*/</span></span><br><span class="line">	j = <span class="number">-1</span>;<span class="comment">/*j初始为-1*/</span></span><br><span class="line"><span class="keyword">while</span>(p-&gt;next != <span class="literal">NULL</span> &amp;&amp; p-&gt;next-&gt;next!= <span class="literal">NULL</span> &amp;&amp; j &lt; i - <span class="number">1</span>) </span><br><span class="line"><span class="comment">/*最终让指针p指向数据元素ai-1结点*/</span></span><br><span class="line">	&#123;</span><br><span class="line">		p = p-&gt;next;</span><br><span class="line">		j++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(j != i - <span class="number">1</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;删除位置参数错！&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line">	q= p-&gt;next; <span class="comment">/*指针s指向数据元素ai结点*/</span></span><br><span class="line">	*x = s-&gt;data;<span class="comment">/*把指针s所指结点的数据元素域值赋予x*/</span></span><br><span class="line">	p-&gt;next = s-&gt;next;<span class="comment">/*把数据元素ai结点从单链表中删除*/</span></span><br><span class="line">	<span class="built_in">free</span>(s);<span class="comment">/*释放指针s所指结点的内存空间*/</span></span><br><span class="line">	<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ListGet</span><span class="params">(SLNode *head, <span class="keyword">int</span> i, DataType *x)</span></span></span><br><span class="line"><span class="function"><span class="comment">/*取数据元素ai和删除函数类同，只是不删除数据元素ai结点*/</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *p;</span><br><span class="line">	<span class="keyword">int</span> j;</span><br><span class="line">	p = head;</span><br><span class="line">	j = <span class="number">-1</span>;</span><br><span class="line">	<span class="keyword">while</span>(p-&gt;next != <span class="literal">NULL</span> &amp;&amp; j &lt; i)</span><br><span class="line">	&#123;</span><br><span class="line">		p = p-&gt;next;j++;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(j != i)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;取元素位置参数错！&quot;</span>);</span><br><span class="line">	<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	*x = p-&gt;data;</span><br><span class="line">	<span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Destroy</span><span class="params">(SLNode **head)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *p, *p1;</span><br><span class="line">	p = *head;</span><br><span class="line">	<span class="keyword">while</span>(p != <span class="literal">NULL</span>)</span><br><span class="line">	&#123;</span><br><span class="line">		p1 = p;</span><br><span class="line">		p = p-&gt;next;</span><br><span class="line">		<span class="built_in">free</span>(p1);</span><br><span class="line">	&#125;</span><br><span class="line">	*head = <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">	<span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	SLNode *head;</span><br><span class="line">	<span class="keyword">int</span> i , x;</span><br><span class="line">	ListInitiate(&amp;head);<span class="comment">/*初始化*/</span></span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; <span class="number">10</span>; i++)</span><br><span class="line">	&#123;</span><br><span class="line">		<span class="keyword">if</span>(ListInsert(head, i, i+<span class="number">1</span>) == <span class="number">0</span>) <span class="comment">/*插入10个数据元素*/</span></span><br><span class="line">		&#123;</span><br><span class="line">			<span class="built_in">printf</span>(<span class="string">&quot;错误! \\n&quot;</span>);</span><br><span class="line">			rturn;</span><br><span class="line">		&#125;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">if</span>(ListDelete(head, <span class="number">4</span>, &amp;x) == <span class="number">0</span>) <span class="comment">/*删除数据元素5*/</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;错误! \\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">for</span>(i = <span class="number">0</span>; i &lt; ListLength(head); i++)</span><br><span class="line">	&#123;</span><br><span class="line">	<span class="keyword">if</span>(ListGet(head, i, &amp;x) == <span class="number">0</span>) <span class="comment">/*取元素*/</span></span><br><span class="line">	&#123;</span><br><span class="line">		<span class="built_in">printf</span>(<span class="string">&quot;错误! \\n&quot;</span>);</span><br><span class="line">		<span class="keyword">return</span>;</span><br><span class="line">	&#125;</span><br><span class="line">	<span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;%d   &quot;</span>, x);<span class="comment">/*显示数据元素*/</span></span><br><span class="line">	&#125;</span><br><span class="line">	Destroy(&amp;head);</span><br><span class="line">	&#125;</span><br></pre></td></tr></table></figure>

<h2 id="三、实验任务"><a href="#三、实验任务" class="headerlink" title="三、实验任务"></a>三、<strong>实验任务</strong></h2><p>1.改正上述程序中的错误。</p>
<p>2.编写合并函数，将两个有序的单链表合并成一个有序单链表。</p>
<p>3.完成实验报告的撰写。</p>
<h1 id="实验三、栈的实现及应用"><a href="#实验三、栈的实现及应用" class="headerlink" title="实验三、栈的实现及应用"></a><strong>实验三、栈的实现及应用</strong></h1><h2 id="一、实验目的-2"><a href="#一、实验目的-2" class="headerlink" title="一、实验目的"></a><strong>一、实验目的</strong></h2><p>1.掌握栈的存储表示和实现</p>
<p>2.掌握栈的基本操作实现。</p>
<p>3.掌握栈在解决实际问题中的应用。</p>
<h2 id="二、实验要求-2"><a href="#二、实验要求-2" class="headerlink" title="二、实验要求"></a><strong>二、实验要求</strong></h2><p>问题描述：设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。</p>
<p>（1）输入的形式：表达式，例如2*(3+4)#</p>
<p>包含的运算符只能有’+’ 、’-‘ 、’*’ 、’/‘ 、’(‘、 ‘)’，“#”代表输入结束符；</p>
<p>（2）输出的形式：运算结果，例如2*(3+4)=14； （3）程序所能达到的功能：对表达式求值并输出。</p>
<h2 id="三、解题参考思路"><a href="#三、解题参考思路" class="headerlink" title="三、解题参考思路"></a><strong>三、解题参考思路</strong></h2><p>为了实现用栈计算算数表达式的值，需设置两个工作栈：用于存储运算符的栈opter，以及用于存储操作数及中间结果的栈opnd。</p>
<p>算法基本思想如下：</p>
<p>（1）首先将操作数栈opnd设为空栈，而将’#’作为运算符栈opter的栈底元素，这样的目的是判断表达式是否求值完毕。</p>
<p>（2）依次读入表达式的每个字，表达式须以’#’结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：</p>
<ol>
<li>若top的优先级小于c，即top&lt;c，则将c直接入栈opter，并读入下一字符赋值给c；</li>
<li>若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;</li>
<li>若top优先级高于c，即top&gt;c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’，此时求值结束。</li>
</ol>
<p>算符间的优先关系如下表所示（表来源：严蔚敏《数据结构》）：</p>
<p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072431.png" alt="表来源：严蔚敏《数据结构》"></p>
<p>表中需要注意的是θ1为opter的栈顶元素，θ2为从表达式中读取的操作符，此优先级表可以用二维数组实现。</p>
<p>图例：</p>
<p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072444.png" alt="表达式求值"></p>
<p>比较算符优先关系代码示例：</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="number">1.</span>	<span class="function"><span class="keyword">int</span> <span class="title">getIndex</span><span class="params">(<span class="keyword">char</span> theta)</span>   <span class="comment">//获取theta所对应的索引  </span></span></span><br><span class="line"><span class="function">2.	</span>&#123;  </span><br><span class="line"><span class="number">3.</span>	    <span class="keyword">int</span> index = <span class="number">0</span>;  </span><br><span class="line"><span class="number">4.</span>	    <span class="keyword">switch</span> (theta)  </span><br><span class="line"><span class="number">5.</span>	    &#123;  </span><br><span class="line"><span class="number">6.</span>	    <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line"><span class="number">7.</span>	        index = <span class="number">0</span>;  </span><br><span class="line"><span class="number">8.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">9.</span>	    <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:  </span><br><span class="line"><span class="number">10.</span>	        index = <span class="number">1</span>;  </span><br><span class="line"><span class="number">11.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">12.</span>	    <span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:  </span><br><span class="line"><span class="number">13.</span>	        index = <span class="number">2</span>;  </span><br><span class="line"><span class="number">14.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">15.</span>	    <span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:  </span><br><span class="line"><span class="number">16.</span>	        index = <span class="number">3</span>;  </span><br><span class="line"><span class="number">17.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">18.</span>	    <span class="keyword">case</span> <span class="string">&#x27;(&#x27;</span>:  </span><br><span class="line"><span class="number">19.</span>	        index = <span class="number">4</span>;  </span><br><span class="line"><span class="number">20.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">21.</span>	    <span class="keyword">case</span> <span class="string">&#x27;)&#x27;</span>:  </span><br><span class="line"><span class="number">22.</span>	        index = <span class="number">5</span>;  </span><br><span class="line"><span class="number">23.</span>	        <span class="keyword">break</span>;  </span><br><span class="line"><span class="number">24.</span>	    <span class="keyword">case</span> <span class="string">&#x27;#&#x27;</span>:  </span><br><span class="line"><span class="number">25.</span>	        index = <span class="number">6</span>;  </span><br><span class="line"><span class="number">26.</span>	    <span class="keyword">default</span>:<span class="keyword">break</span>;  </span><br><span class="line"><span class="number">27.</span>	    &#125;  </span><br><span class="line"><span class="number">28.</span>	    <span class="keyword">return</span> index;  </span><br><span class="line"><span class="number">29.</span>	&#125;  </span><br><span class="line"><span class="number">30.</span>	  </span><br><span class="line"><span class="number">31.</span>	<span class="function"><span class="keyword">char</span> <span class="title">getPriority</span><span class="params">(<span class="keyword">char</span> theta1, <span class="keyword">char</span> theta2)</span>   <span class="comment">//获取theta1与theta2之间的优先级  </span></span></span><br><span class="line"><span class="function">32.	</span>&#123;  </span><br><span class="line"><span class="number">33.</span>	    <span class="keyword">const</span> <span class="keyword">char</span> priority[][<span class="number">7</span>] =     <span class="comment">//算符间的优先级关系  </span></span><br><span class="line"><span class="number">34.</span>	    &#123;  </span><br><span class="line"><span class="number">35.</span>	        &#123; <span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">36.</span>	        &#123; <span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">37.</span>	        &#123; <span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">38.</span>	        &#123; <span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">39.</span>	        &#123; <span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;=&#x27;</span>,<span class="string">&#x27;0&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">40.</span>	        &#123; <span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;0&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span>,<span class="string">&#x27;&gt;&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">41.</span>	        &#123; <span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;&lt;&#x27;</span>,<span class="string">&#x27;0&#x27;</span>,<span class="string">&#x27;=&#x27;</span> &#125;,  </span><br><span class="line"><span class="number">42.</span>	    &#125;;  </span><br><span class="line"><span class="number">43.</span>	  </span><br><span class="line"><span class="number">44.</span>	    <span class="keyword">int</span> index1 = getIndex(theta1);  </span><br><span class="line"><span class="number">45.</span>	    <span class="keyword">int</span> index2 = getIndex(theta2);  </span><br><span class="line"><span class="number">46.</span>	    <span class="keyword">return</span> priority[index1][index2];  </span><br><span class="line"><span class="number">47.</span>	&#125;</span><br></pre></td></tr></table></figure>

<h2 id="四、实验任务-1"><a href="#四、实验任务-1" class="headerlink" title="四、实验任务"></a><strong>四、实验任务</strong></h2><p>认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。</p>
<h2 id="五、实验思路"><a href="#五、实验思路" class="headerlink" title="五、实验思路"></a>五、实验思路</h2><h3 id="栈的定义"><a href="#栈的定义" class="headerlink" title="栈的定义"></a><strong><a href="notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d">栈的定义</a></strong></h3><p>创建两个结构体，一个做栈，一个是栈的节点</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">node</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> data;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">node</span> *<span class="title">next</span>;</span></span><br><span class="line">&#125;Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">stack</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    Node *top;</span><br><span class="line">    <span class="keyword">int</span> count;</span><br><span class="line">&#125;Stack;</span><br></pre></td></tr></table></figure>

<h3 id="栈的操作"><a href="#栈的操作" class="headerlink" title="栈的操作"></a><strong><a href="notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d">栈的操作</a></strong></h3><p>包括栈的基本操作</p>
<ol>
<li>栈的初始化</li>
<li>栈空的判断</li>
<li>压栈</li>
<li>出栈</li>
<li>取栈顶元素</li>
<li>清空栈</li>
</ol>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="comment">//初始化栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">InitStack</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    s-&gt;top = <span class="literal">NULL</span>;</span><br><span class="line">    s-&gt;count= <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//判空栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">EmptyStack</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (s-&gt;count == <span class="number">0</span>) ? OK : ERROR;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//压栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Push</span><span class="params">(Stack *s, <span class="keyword">int</span> e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    Node *p = (Node *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(Node));</span><br><span class="line">    <span class="keyword">if</span>(p == <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    p-&gt;data = e;</span><br><span class="line">    p-&gt;next = s-&gt;top;</span><br><span class="line">    s-&gt;top = p;</span><br><span class="line">    s-&gt;count++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//取栈顶元素</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">GetTop</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">NULL</span> == s-&gt;top)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (s-&gt;top-&gt;data);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//出栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Pop</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> e;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">NULL</span> == s-&gt;top)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Node *p = s-&gt;top;</span><br><span class="line">    e = p-&gt;data;</span><br><span class="line">    s-&gt;top = p-&gt;next;</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">    s-&gt;count--;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> e;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//清空栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ClearStack</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s-&gt;count &lt;= <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;栈已空&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    Node *p = s-&gt;top;</span><br><span class="line">    <span class="keyword">while</span>(s-&gt;count &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        p=s-&gt;top;</span><br><span class="line">        s-&gt;top=s-&gt;top-&gt;next;</span><br><span class="line">        <span class="built_in">free</span>(p);</span><br><span class="line">        s-&gt;count--;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    s-&gt;top==<span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="符号优先级判断函数"><a href="#符号优先级判断函数" class="headerlink" title="符号优先级判断函数"></a><strong><a href="notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d">符号优先级判断函数</a></strong></h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Priority</span><span class="params">(<span class="keyword">char</span> s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">switch</span>(s)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;(&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="主函数思路1"><a href="#主函数思路1" class="headerlink" title="主函数思路1"></a><strong><a href="notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d">主函数思路1</a></strong></h3><ol>
<li>判断符号还是数字，数字直接入栈</li>
<li>判断符号<ol>
<li>如果是（符号栈为空||符号栈栈顶为’(‘&amp;&amp;当前符号不是’)’||栈顶优先级低于当前符号),则入栈不计算</li>
<li>如果’()’内无其他运算符，即最栈顶是（当前操作符号是），直接（出栈</li>
<li>如果（字符串扫描完成且符号栈不为空）||(当前运算符优先级低于栈顶元素)</li>
</ol>
</li>
</ol>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    Stack num, opt;</span><br><span class="line">    <span class="keyword">char</span> l = <span class="string">&#x27;*&#x27;</span>;</span><br><span class="line">    <span class="keyword">char</span> str[<span class="number">100</span>] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="keyword">int</span> i = <span class="number">0</span>, tmp = <span class="number">0</span>, j;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span> (InitStack(&amp;num) != OK || InitStack(&amp;opt) != OK) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;Init Failure!\\n&quot;</span>);</span><br><span class="line">        <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(l != <span class="string">&#x27;#&#x27;</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;Please Input Operator :\\n&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>, str);</span><br><span class="line">        <span class="keyword">if</span>(str[<span class="number">0</span>]==<span class="string">&#x27;#&#x27;</span>)<span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">while</span> (str[i] != <span class="string">&#x27;\\0&#x27;</span> || EmptyStack(&amp;opt) != OK) &#123;</span><br><span class="line">            <span class="keyword">if</span> (str[i] &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; str[i] &lt;= <span class="string">&#x27;9&#x27;</span>) &#123;</span><br><span class="line">                tmp = tmp * <span class="number">10</span> + str[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">                i++;</span><br><span class="line">                <span class="keyword">if</span> (str[i] &lt; <span class="string">&#x27;0&#x27;</span> || str[i] &gt; <span class="string">&#x27;9&#x27;</span>) &#123;</span><br><span class="line">                    Push(&amp;num, tmp);</span><br><span class="line">                    tmp = <span class="number">0</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="comment">//符号栈为空</span></span><br><span class="line">                <span class="comment">//符号栈栈顶为&#x27;(&#x27;&amp;&amp;当前符号不是&#x27;)&#x27;</span></span><br><span class="line">                <span class="comment">//栈顶优先级低于当前符号</span></span><br><span class="line">                <span class="keyword">if</span> ((EmptyStack(&amp;opt) == OK) || (GetTop(&amp;opt) == <span class="string">&#x27;(&#x27;</span> &amp;&amp; str[i] != <span class="string">&#x27;)&#x27;</span>) || Priority(str[i]) &gt; Priority(GetTop(&amp;opt)))<span class="comment">//进栈不参与运算</span></span><br><span class="line">                &#123;</span><br><span class="line">                    Push(&amp;opt, str[i]);</span><br><span class="line">                    i++;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="comment">//&#x27;()&#x27;内无其他运算符</span></span><br><span class="line">                <span class="keyword">if</span> (GetTop(&amp;opt) == <span class="string">&#x27;(&#x27;</span> &amp;&amp; str[i] == <span class="string">&#x27;)&#x27;</span>)<span class="comment">//出栈不参与运算</span></span><br><span class="line">                &#123;</span><br><span class="line">                    Pop(&amp;opt);</span><br><span class="line">                    i++;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="comment">//</span></span><br><span class="line">                <span class="keyword">if</span> ((str[i] == <span class="string">&#x27;\\0&#x27;</span> &amp;&amp; EmptyStack(&amp;opt) != OK) || (str[i] == <span class="string">&#x27;)&#x27;</span> &amp;&amp; GetTop(&amp;opt) != <span class="string">&#x27;(&#x27;</span>) || Priority(str[i]) &lt;= Priority(GetTop(&amp;opt)))<span class="comment">//出栈并参与运算</span></span><br><span class="line">                &#123;</span><br><span class="line">                    <span class="keyword">switch</span> (Pop(&amp;opt)) &#123;</span><br><span class="line">                        <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">                            Push(&amp;num, Pop(&amp;num) + Pop(&amp;num));</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">                            j = Pop(&amp;num);</span><br><span class="line">                            Push(&amp;num, Pop(&amp;num) - j);</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        <span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">                            Push(&amp;num, Pop(&amp;num) * Pop(&amp;num));</span><br><span class="line">                            <span class="keyword">break</span>;</span><br><span class="line">                        <span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">                            j = Pop(&amp;num);</span><br><span class="line">                            Push(&amp;num, Pop(&amp;num) / j);</span><br><span class="line">                    &#125;</span><br><span class="line">                    <span class="keyword">continue</span>;</span><br><span class="line">                &#125;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line"></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>, Pop(&amp;num));</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;\\n&quot;</span>);</span><br><span class="line">        i=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="主函数思路2：数据结构指导书要求"><a href="#主函数思路2：数据结构指导书要求" class="headerlink" title="主函数思路2：数据结构指导书要求"></a><strong><a href="notion://www.notion.so/afc75248d48d4c3baadfce4b9c10a03d">主函数思路2：数据结构指导书要求</a></strong></h3><ol>
<li>首先创建两个栈opnd、opter，设为opnd为空栈，而将’#’作为运算符栈opter的栈底元素，以判断表达式是否求值完毕。</li>
<li>依次读入表达式的每个字，表达式须以’#’结，读入字符若是操作数则入栈opnd，读入字符若是运算符，则将此运算符c与opter的栈顶元素top比较优先级后执行相应的操作，具体操作如下：<ol>
<li>若top的优先级小于c，即top&lt;c，则将c直接入栈opter，并读入下一字符赋值给c；</li>
<li>若top的优先级等于c，即top=c，则弹出opter的栈顶元素，并读入下一字符赋值给c，这一步目的是进行括号操作;</li>
<li>若top优先级高于c，即top&gt;c，则表明可以计算，此时弹出opnd的栈顶两个元素，并且弹出opter栈顶的的运算符，计算后将结果放入栈opnd中。直至opter的栈顶元素和当前读入的字符均为’#’，此时求值结束。</li>
</ol>
</li>
</ol>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;strings.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK     1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR  0</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_LINE 100</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">nodeNum</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="keyword">int</span> data;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">node</span> *<span class="title">next</span>;</span></span><br><span class="line">&#125;Node;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">stack</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    Node *top;</span><br><span class="line">    <span class="keyword">int</span> count;</span><br><span class="line">&#125;Stack;</span><br><span class="line"></span><br><span class="line"><span class="comment">//初始化栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">InitStack</span><span class="params">(Stack *l)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    l-&gt;top = <span class="literal">NULL</span>;</span><br><span class="line">    l-&gt;count= <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//判空栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">EmptyStack</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> (s-&gt;count == <span class="number">0</span>) ? OK : ERROR;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//压栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Push</span><span class="params">(Stack *s, <span class="keyword">int</span> e)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    Node *p = (Node *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(Node));</span><br><span class="line">    <span class="keyword">if</span>(p == <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    p-&gt;data = e;</span><br><span class="line">    p-&gt;next = s-&gt;top;</span><br><span class="line">    s-&gt;top = p;</span><br><span class="line">    s-&gt;count++;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//取栈顶元素</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">GetTop</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">NULL</span> == s-&gt;top)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> (s-&gt;top-&gt;data);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//符号优先级判断</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Priority</span><span class="params">(<span class="keyword">char</span> s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">switch</span>(s)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;(&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">3</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">2</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">1</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="string">&#x27;#&#x27;</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//出栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">Pop</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> e;</span><br><span class="line">    <span class="keyword">if</span>(<span class="literal">NULL</span> == s-&gt;top)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    Node *p = s-&gt;top;</span><br><span class="line">    e = p-&gt;data;</span><br><span class="line">    s-&gt;top = p-&gt;next;</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">    s-&gt;count--;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">return</span> e;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//清空栈</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">ClearStack</span><span class="params">(Stack *s)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(s-&gt;count &lt;= <span class="number">0</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;栈已空&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    Node *p = s-&gt;top;</span><br><span class="line">    <span class="keyword">while</span>(s-&gt;count &gt; <span class="number">0</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        p=s-&gt;top;</span><br><span class="line">        s-&gt;top=s-&gt;top-&gt;next;</span><br><span class="line">        <span class="built_in">free</span>(p);</span><br><span class="line">        s-&gt;count--;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    s-&gt;top==<span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="keyword">char</span> str[MAX_LINE] = &#123;<span class="string">&quot;123&quot;</span>&#125;;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,temp=<span class="number">0</span>,j=<span class="number">0</span>;</span><br><span class="line">    Stack opnd,opter;</span><br><span class="line"></span><br><span class="line">    <span class="keyword">if</span>(InitStack(&amp;opnd) != OK || InitStack(&amp;opter) != OK)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;初始化错误，请关闭后重试&quot;</span>);</span><br><span class="line">        <span class="built_in">exit</span>(<span class="number">1</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    Push(&amp;opter,<span class="string">&#x27;#&#x27;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">do</span>&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;请输入计算表达式,并以#结尾\\n&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,str);</span><br><span class="line">    &#125;<span class="keyword">while</span>(str[<span class="number">0</span>]== <span class="string">&#x27;#&#x27;</span>|| str[<span class="built_in">strlen</span>(str)<span class="number">-1</span>] != <span class="string">&#x27;#&#x27;</span>);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(str[i] != <span class="string">&#x27;#&#x27;</span> || GetTop(&amp;opter) != <span class="string">&#x27;#&#x27;</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span>(str[i] &gt;= <span class="string">&#x27;0&#x27;</span> &amp;&amp; str[i] &lt;= <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">        &#123;</span><br><span class="line">            temp = temp * <span class="number">10</span> + str[i] - <span class="string">&#x27;0&#x27;</span>;</span><br><span class="line">            i++;</span><br><span class="line">            <span class="keyword">if</span>(str[i] &lt; <span class="string">&#x27;0&#x27;</span> || str[i] &gt; <span class="string">&#x27;9&#x27;</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                Push(&amp;opnd,temp);</span><br><span class="line">                temp = <span class="number">0</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;<span class="keyword">else</span>&#123;</span><br><span class="line">            <span class="comment">//符号栈栈底是#</span></span><br><span class="line">            <span class="comment">//符号栈栈顶为&#x27;(&#x27;&amp;&amp;当前符号不是&#x27;)&#x27;</span></span><br><span class="line">            <span class="comment">//栈顶优先级低于当前符号</span></span><br><span class="line">            <span class="comment">//进栈不参与运算</span></span><br><span class="line">            <span class="keyword">if</span> ((GetTop(&amp;opter) == <span class="string">&#x27;#&#x27;</span>) || (GetTop(&amp;opter) == <span class="string">&#x27;(&#x27;</span> &amp;&amp; str[i] != <span class="string">&#x27;)&#x27;</span>) || Priority(str[i]) &gt; Priority(GetTop(&amp;opter)))</span><br><span class="line">            &#123;</span><br><span class="line">                Push(&amp;opter, str[i]);</span><br><span class="line">                i++;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//&#x27;()&#x27;内无其他运算符</span></span><br><span class="line">            <span class="comment">//出栈不参与运算</span></span><br><span class="line">            <span class="keyword">if</span> (GetTop(&amp;opter) == <span class="string">&#x27;(&#x27;</span> &amp;&amp; str[i] == <span class="string">&#x27;)&#x27;</span>)</span><br><span class="line">            &#123;</span><br><span class="line">                Pop(&amp;opter);</span><br><span class="line">                i++;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">            <span class="comment">//</span></span><br><span class="line">            <span class="comment">//出栈运算</span></span><br><span class="line">            <span class="keyword">if</span> ((str[i] == <span class="string">&#x27;#&#x27;</span> &amp;&amp; GetTop(&amp;opter) != <span class="string">&#x27;#&#x27;</span>) || (str[i] == <span class="string">&#x27;)&#x27;</span> &amp;&amp; GetTop(&amp;opter) != <span class="string">&#x27;(&#x27;</span>) || Priority(str[i]) &lt;= Priority(GetTop(&amp;opter)))</span><br><span class="line">            &#123;</span><br><span class="line">                <span class="keyword">switch</span> (Pop(&amp;opter)) &#123;</span><br><span class="line">                    <span class="keyword">case</span> <span class="string">&#x27;+&#x27;</span>:</span><br><span class="line">                        Push(&amp;opnd, Pop(&amp;opnd) + Pop(&amp;opnd));</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    <span class="keyword">case</span> <span class="string">&#x27;-&#x27;</span>:</span><br><span class="line">                        j = Pop(&amp;opnd);</span><br><span class="line">                        Push(&amp;opnd, Pop(&amp;opnd) - j);</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    <span class="keyword">case</span> <span class="string">&#x27;*&#x27;</span>:</span><br><span class="line">                        Push(&amp;opnd, Pop(&amp;opnd) * Pop(&amp;opnd));</span><br><span class="line">                        <span class="keyword">break</span>;</span><br><span class="line">                    <span class="keyword">case</span> <span class="string">&#x27;/&#x27;</span>:</span><br><span class="line">                        j = Pop(&amp;opnd);</span><br><span class="line">                        Push(&amp;opnd, Pop(&amp;opnd) / j);</span><br><span class="line">                &#125;</span><br><span class="line">                <span class="keyword">continue</span>;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>, Pop(&amp;opnd));</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\\n&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h1 id="实验四、队列的实现及应用"><a href="#实验四、队列的实现及应用" class="headerlink" title="实验四、队列的实现及应用"></a><strong>实验四、队列的实现及应用</strong></h1><blockquote>
<p><strong>一、实验目的</strong></p>
</blockquote>
<blockquote>
<p>1.掌握队列的存储表示和实现。</p>
</blockquote>
<blockquote>
<p>2.掌握队列的基本操作实现。</p>
</blockquote>
<blockquote>
<p>3.掌握队列在解决实际问题中的应用。</p>
</blockquote>
<blockquote>
<p><strong>二、实验要求</strong></p>
</blockquote>
<p>利用队列模拟服务台前的排队现象问题。</p>
<p>某银行有一个客户办理业务站，在单位时间内随机地有客户到达，设每位客户的业务办理时间是某个范围的随机值。设只有一个窗口，一位业务人员，要求程序模拟统计在设定时间内，业务人员的总空闲时间和客户的平均等待时间。假定模拟数据已按客户到达的先后顺序依次存于某个正文数据文件中，对应每位客户有两个数据：到达时间和需要办理业务的时间，文本文件内容如：10 20 10 10 45 5 55 10 58 15 65 10</p>
<h2 id="三、解题参考思路-1"><a href="#三、解题参考思路-1" class="headerlink" title="三、解题参考思路"></a>三、<strong>解题参考思路</strong></h2><p>与栈相对应，队列是一种先进先出的线性表。它只允许在表的一端进行插入，而在另一端进行删除元素。允许插入的一端称队尾，允许删除的一端称队头。插入与删除分别称为入队与出队。队列示意图如下图所示：</p>
<h3 id="一、数据描述（结构体定义）"><a href="#一、数据描述（结构体定义）" class="headerlink" title="一、数据描述（结构体定义）"></a>一、数据描述（结构体定义）</h3><p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072551.png" alt="数据描述（结构体定义）"></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">  <span class="keyword">int</span> arrive;</span><br><span class="line">  <span class="keyword">int</span> treat;<span class="comment">//客户的信息结构</span></span><br><span class="line">&#125;QNODE；</span><br><span class="line">    </span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">	QNODE data;</span><br><span class="line">	Struct node *next;<span class="comment">//队列中的元素信息</span></span><br><span class="line">&#125;LNODE,*QueuePtr;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span>  <span class="class"><span class="keyword">struct</span>&#123;</span> <span class="comment">//链队列类型</span></span><br><span class="line">  QueuePtr   front ;  <span class="comment">//队头指针    </span></span><br><span class="line">  QueuePtr   rear ;  <span class="comment">//队尾指针</span></span><br><span class="line">&#125; LinkQueue;</span><br></pre></td></tr></table></figure>

<h3 id="二、存取操作（队列操作函数）"><a href="#二、存取操作（队列操作函数）" class="headerlink" title="二、存取操作（队列操作函数）"></a>二、存取操作（队列操作函数）</h3><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：队列初始化</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">InitQueue</span><span class="params">(LinkQueue *Q)</span></span>&#123;</span><br><span class="line">    QueuePtr p =(QueuePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LNODE));</span><br><span class="line">    <span class="keyword">if</span> (p == <span class="literal">NULL</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;初始化失败\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    Q-&gt;rear = Q-&gt;front = p;</span><br><span class="line">    Q-&gt;front-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：入队</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针 入队数据</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">EnQueue</span><span class="params">(LinkQueue* Q,QNODE data)</span></span>&#123;</span><br><span class="line">    QueuePtr p =(QueuePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LNODE));</span><br><span class="line">    p-&gt;data = data;</span><br><span class="line">    p-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    Q-&gt;rear-&gt;next = p;</span><br><span class="line">    Q-&gt;rear = p;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/* 函数功能：出队</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针 取值变量指针</span></span><br><span class="line"><span class="comment"> * 传入参数：无</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">DeQueue</span><span class="params">(LinkQueue *Q,QNODE *e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == Q-&gt;rear) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;队列为空，删除失败\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    LNODE* p;</span><br><span class="line">    p = Q-&gt;front-&gt;next;</span><br><span class="line">    *e = p-&gt;data;</span><br><span class="line">    Q-&gt;front-&gt;next = p-&gt;next;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;rear == p)Q-&gt;rear = Q-&gt;front;</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="三、主函数流程"><a href="#三、主函数流程" class="headerlink" title="三、主函数流程"></a>三、主函数流程</h2><p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072634.png" alt="主函数流程"></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">&#123; </span><br><span class="line">	设置统计初值：业务员等待时间，客户总的待时间，客户总人数等</span><br><span class="line"></span><br><span class="line">	设置当前时钟clock时间为<span class="number">0</span>；</span><br><span class="line">	<span class="comment">//用变量clock来模拟当前时间.</span></span><br><span class="line"></span><br><span class="line">	打开数据文件，准备读；</span><br><span class="line">	<span class="built_in">printf</span>(<span class="string">&quot;\\nenterfilename:&quot;</span>);</span><br><span class="line">  <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,Fname);<span class="comment">/*输入装客户模拟数据的文件的文件名*/</span></span><br><span class="line"></span><br><span class="line">	读入第一位客户信息于暂存变量中；</span><br><span class="line">	<span class="comment">//文件读操作have= fscanf(fp,&quot;%d %d&quot;,&amp;temp.arrive,&amp;temp.treat);</span></span><br><span class="line"></span><br><span class="line">	<span class="comment">//约定每轮循环，处理完一位客户</span></span><br><span class="line">	<span class="keyword">do</span>&#123;</span><br><span class="line">			<span class="keyword">if</span>(等待队列为空，并且还有客户)&#123; </span><br><span class="line"></span><br><span class="line">				累计业务员总等待时间；</span><br><span class="line"></span><br><span class="line">				时钟推进到暂存变量中的客户的到达时间；<span class="comment">//clock=temp.arrive</span></span><br><span class="line"></span><br><span class="line">				暂存变量中的客户信息进队；</span><br><span class="line"></span><br><span class="line">				读取下一位客户信息于暂存变量；</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">从等待队列出队一位客户；</span><br><span class="line"></span><br><span class="line">累计客户人数；</span><br><span class="line"></span><br><span class="line">将该客户的等待时间累计到客户的总等待时间；<span class="comment">//=当前时间-客户到达时间</span></span><br><span class="line"></span><br><span class="line">设定当前客户的业务办理结束时间；<span class="comment">//=当前时间+客户办理业务所需时间</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(下一位客户的到达时间在当前客户处理结束之前，并且还有客户)</span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line">		暂存变量中的客户信息进队；</span><br><span class="line"></span><br><span class="line">读取下一位客户信息于暂存变量；</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">		时钟推进到当前客户办理结束时间；</span><br><span class="line"></span><br><span class="line">&#125;<span class="keyword">while</span>(还有未处理的客户)；<span class="comment">//等待队列不为空或者还有客户（have==2）</span></span><br><span class="line"></span><br><span class="line">计算统计结果，并输出；</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    QNODE curret,temp;</span><br><span class="line">    <span class="keyword">int</span> dwait=<span class="number">0</span>,clock=<span class="number">0</span>,wait=<span class="number">0</span>,count=<span class="number">0</span>,have=<span class="number">0</span>,finish;</span><br><span class="line">    LinkQueue BankQueue;</span><br><span class="line">    InitQueue(&amp;BankQueue);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\\n请输入读取文件的文件名\\n&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,file_name);</span><br><span class="line">    fopen_s(&amp;fp,file_name,<span class="string">&quot;r&quot;</span>);</span><br><span class="line">    <span class="keyword">while</span> (fp == <span class="literal">NULL</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;当前目录没有此文件，请重新输入文件名&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,file_name);</span><br><span class="line">    &#125;</span><br><span class="line">    have = fscanf_s(fp,<span class="string">&quot;%d %d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">    <span class="keyword">do</span>&#123;        <span class="comment">//约定每轮循环，处理一个客户</span></span><br><span class="line">        <span class="keyword">if</span>(BankQueue.front-&gt;next == <span class="literal">NULL</span>&amp;&amp;have==<span class="number">2</span>)     <span class="comment">//等待队列为空，但还有客户</span></span><br><span class="line">        &#123;</span><br><span class="line">            dwait+=temp.arrive-clock;  <span class="comment">//累计业务员总等待时间</span></span><br><span class="line">            clock=temp.arrive;</span><br><span class="line">            EnQueue(&amp;BankQueue,temp); <span class="comment">//暂存变量中客户的信息进队</span></span><br><span class="line">            have=<span class="built_in">fscanf</span>(fp,<span class="string">&quot;%d %d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">        &#125;</span><br><span class="line">        count++;</span><br><span class="line">        DeQueue(&amp;BankQueue,&amp;curret); <span class="comment">//出队一位客户信息</span></span><br><span class="line">        wait+=clock-curret.arrive;  <span class="comment">//累计到客户的等待时间</span></span><br><span class="line">        finish=clock+curret.treat;  <span class="comment">//设定业务办理结束时间</span></span><br><span class="line">        <span class="keyword">while</span>(have==<span class="number">2</span>&amp;&amp;temp.arrive&lt;=finish)   <span class="comment">//下一位客户到达时间在当前客户处理结束之前</span></span><br><span class="line">        &#123;</span><br><span class="line">            EnQueue(&amp;BankQueue,temp);  <span class="comment">//暂存变量中的客户信息进队</span></span><br><span class="line">            have=<span class="built_in">fscanf</span>(fp,<span class="string">&quot;%d%d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">        &#125;</span><br><span class="line">        clock=finish;  <span class="comment">//时钟推进到当前客户办理结束时间</span></span><br><span class="line">    &#125;<span class="keyword">while</span>(have==<span class="number">2</span>||BankQueue.front-&gt;next!=<span class="literal">NULL</span>);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;结果：业务员等待时间%d\\n客户平均等待时间%f\\n&quot;</span>,dwait,(<span class="keyword">double</span>)wait/count);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;模拟总时间：%d,\\n客户人数：%d,\\n总等待时间：%d\\n&quot;</span>,clock,count,wait);</span><br><span class="line">    getchar();</span><br><span class="line">&#125;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;malloc.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_FILE_NAME_LENGHT 120</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> OK 1</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> ERROR 0</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//客户的信息结构</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> arrive;</span><br><span class="line">    <span class="keyword">int</span> treat;</span><br><span class="line">&#125;QNODE;</span><br><span class="line"></span><br><span class="line"><span class="comment">//队列节点定义结构</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">    QNODE data;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">node</span> *<span class="title">next</span>;</span><span class="comment">//队列中的元素信息</span></span><br><span class="line">&#125;LNODE,*QueuePtr;</span><br><span class="line"></span><br><span class="line"><span class="comment">//队列-链队列类型</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    QueuePtr  front ; <span class="comment">//队头指针</span></span><br><span class="line">    QueuePtr  rear ; <span class="comment">//队尾指针</span></span><br><span class="line">&#125;LinkQueue;</span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> file_name[MAX_FILE_NAME_LENGHT];</span><br><span class="line">FILE *fp;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：队列初始化</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">InitQueue</span><span class="params">(LinkQueue *Q)</span></span>&#123;</span><br><span class="line">    QueuePtr p =(QueuePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LNODE));</span><br><span class="line">    <span class="keyword">if</span> (p == <span class="literal">NULL</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;初始化失败\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    Q-&gt;rear = Q-&gt;front = p;</span><br><span class="line">    Q-&gt;front-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 函数功能：入队</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针 入队数据</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">EnQueue</span><span class="params">(LinkQueue* Q,QNODE data)</span></span>&#123;</span><br><span class="line">    QueuePtr p =(QueuePtr)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LNODE));</span><br><span class="line">    p-&gt;data = data;</span><br><span class="line">    p-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    Q-&gt;rear-&gt;next = p;</span><br><span class="line">    Q-&gt;rear = p;</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/* 函数功能：出队</span></span><br><span class="line"><span class="comment"> * 传入参数：队列指针 取值变量指针</span></span><br><span class="line"><span class="comment"> * 传入参数：无</span></span><br><span class="line"><span class="comment"> * 返回值：int 1 OK 操作成功</span></span><br><span class="line"><span class="comment"> *       int 1 ERROE 操作失败</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">DeQueue</span><span class="params">(LinkQueue *Q,QNODE *e)</span></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;front == Q-&gt;rear) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;队列为空，删除失败\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">return</span> ERROR;</span><br><span class="line">    &#125;</span><br><span class="line">    LNODE* p;</span><br><span class="line">    p = Q-&gt;front-&gt;next;</span><br><span class="line">    *e = p-&gt;data;</span><br><span class="line">    Q-&gt;front-&gt;next = p-&gt;next;</span><br><span class="line">    <span class="keyword">if</span> (Q-&gt;rear == p)Q-&gt;rear = Q-&gt;front;</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">    <span class="keyword">return</span> OK;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> *函数功能：模仿模拟服务台前的排队现象问题</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    QNODE curret,temp;</span><br><span class="line">    <span class="keyword">int</span> dwait=<span class="number">0</span>,clock=<span class="number">0</span>,wait=<span class="number">0</span>,count=<span class="number">0</span>,have=<span class="number">0</span>,finish;</span><br><span class="line">    LinkQueue BankQueue;</span><br><span class="line">    InitQueue(&amp;BankQueue);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\\n请输入读取文件的文件名\\n&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,file_name);</span><br><span class="line">    fopen_s(&amp;fp,file_name,<span class="string">&quot;r&quot;</span>);</span><br><span class="line">    <span class="keyword">while</span> (fp == <span class="literal">NULL</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;当前目录没有此文件，请重新输入文件名&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,file_name);</span><br><span class="line">    &#125;</span><br><span class="line">    have = fscanf_s(fp,<span class="string">&quot;%d %d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">    <span class="keyword">do</span>&#123;        <span class="comment">//约定每轮循环，处理一个客户</span></span><br><span class="line">        <span class="keyword">if</span>(BankQueue.front-&gt;next == <span class="literal">NULL</span>&amp;&amp;have==<span class="number">2</span>)     <span class="comment">//等待队列为空，但还有客户</span></span><br><span class="line">        &#123;</span><br><span class="line">            dwait+=temp.arrive-clock;  <span class="comment">//累计业务员总等待时间</span></span><br><span class="line">            clock=temp.arrive;</span><br><span class="line">            EnQueue(&amp;BankQueue,temp); <span class="comment">//暂存变量中客户的信息进队</span></span><br><span class="line">            have=<span class="built_in">fscanf</span>(fp,<span class="string">&quot;%d %d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">        &#125;</span><br><span class="line">        count++;</span><br><span class="line">        DeQueue(&amp;BankQueue,&amp;curret); <span class="comment">//出队一位客户信息</span></span><br><span class="line">        wait+=clock-curret.arrive;  <span class="comment">//累计到客户的等待时间</span></span><br><span class="line">        finish=clock+curret.treat;  <span class="comment">//设定业务办理结束时间</span></span><br><span class="line">        <span class="keyword">while</span>(have==<span class="number">2</span>&amp;&amp;temp.arrive&lt;=finish)   <span class="comment">//下一位客户到达时间在当前客户处理结束之前</span></span><br><span class="line">        &#123;</span><br><span class="line">            EnQueue(&amp;BankQueue,temp);  <span class="comment">//暂存变量中的客户信息进队</span></span><br><span class="line">            have=<span class="built_in">fscanf</span>(fp,<span class="string">&quot;%d%d&quot;</span>,&amp;temp.arrive,&amp;temp.treat);</span><br><span class="line">        &#125;</span><br><span class="line">        clock=finish;  <span class="comment">//时钟推进到当前客户办理结束时间</span></span><br><span class="line">    &#125;<span class="keyword">while</span>(have==<span class="number">2</span>||BankQueue.front-&gt;next!=<span class="literal">NULL</span>);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;结果：业务员等待时间%d\\n客户平均等待时间%f\\n&quot;</span>,dwait,(<span class="keyword">double</span>)wait/count);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;模拟总时间：%d,\\n客户人数：%d,\\n总等待时间：%d\\n&quot;</span>,clock,count,wait);</span><br><span class="line">    getchar();</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="四、实验任务-2"><a href="#四、实验任务-2" class="headerlink" title="四、实验任务"></a>四、实验任务</h2><p>认真阅读与理解实验内容的具体要求，参考教材相关章节，结合实验内容的要求，编写实验程序并上机调试与测试，完成实验报告的撰写。</p>
<h2 id="五、注意点"><a href="#五、注意点" class="headerlink" title="五、注意点"></a><strong>五、注意点</strong></h2><ol>
<li>*<em>fopen()函数原型为FILE * =fopen(char* <em>,char ** );</em></em></li>
<li>**fopen_s函数更改为int fopen_s(FILE <em>,char <em>,char *);</em></em></li>
<li>fscanf_s函数原型为 int fscanf_s(FILE *,char * <em>,dataType</em> *……)</li>
<li>fscanf_s函数原型为 int fscanf_s(FILE *,char * <em>,dataType</em> *……)</li>
<li>被打开的文件<strong>必须与exe文件夹放在一起，或者指定绝对路径</strong></li>
<li>在使用fscanf前确保传入的FILE*不是NULL,否则会出现错误</li>
</ol>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="comment">/*文件操作实例*/</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="keyword">char</span> file_name[<span class="number">150</span>] =<span class="string">&quot;text.txt&quot;</span>;</span><br><span class="line">    <span class="keyword">int</span> data;</span><br><span class="line">    <span class="keyword">int</span> data2;</span><br><span class="line">    FILE *fp;</span><br><span class="line">    <span class="keyword">int</span> l =<span class="number">1</span>;</span><br><span class="line">    fopen_s(&amp;fp,file_name,<span class="string">&quot;r&quot;</span>);</span><br><span class="line">    <span class="keyword">if</span> (fp != <span class="literal">NULL</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;OK&quot;</span>);</span><br><span class="line">        fscanf_s(fp,<span class="string">&quot;%d %d&quot;</span>,&amp;data2,&amp;data);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d %d&quot;</span>,data,data2);</span><br><span class="line">    &#125; <span class="keyword">else</span>&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;Fause&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="实验五、二叉树操作及应用"><a href="#实验五、二叉树操作及应用" class="headerlink" title="实验五、二叉树操作及应用"></a><strong>实验五、二叉树操作及应用</strong></h2><h2 id="一、-实验目的"><a href="#一、-实验目的" class="headerlink" title="一、 实验目的"></a><strong>一、</strong> <strong>实验目的</strong></h2><p>掌握二叉树的定义、结构特征，以及各种存储结构的特点及使用范围，各种遍历算法。掌握用指针类型描述、访问和处理二叉树的运算。掌握前序或中序的非递归遍历算法。</p>
<h2 id="二、相关知识"><a href="#二、相关知识" class="headerlink" title="二、相关知识"></a>二、相关知识</h2><h3 id="遍历"><a href="#遍历" class="headerlink" title="遍历"></a>遍历</h3><p>二叉树的遍历主要有三种：</p>
<p>（1）先(根)序遍历（根左右）</p>
<p>（2）中(根)序遍历（左根右）</p>
<p>（3）后(根)序遍历（左右根）</p>
<p>举个例子：</p>
<p><a target="_blank" rel="noopener" href="https://img-blog.csdn.net/20180704200305280?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODQwMTI5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70">https://img-blog.csdn.net/20180704200305280?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM0ODQwMTI5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70</a></p>
<p>先(根)序遍历（根左右）：A B D H E I C F J K G</p>
<p>中(根)序遍历（左根右） : D H B E I A J F K C G</p>
<p>后(根)序遍历（左右根） : H D I E B J K F G C A</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="class"><span class="keyword">class</span> <span class="title">Node</span>:</span></span><br><span class="line">    def __init__(self, dat, left=None, right=None):</span><br><span class="line">        self.data = dat</span><br><span class="line">        self.left = left</span><br><span class="line">        self.right = right</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line">def rebuild(rear, center):</span><br><span class="line">    <span class="keyword">if</span> <span class="keyword">not</span> rear:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    cur = Node(rear[<span class="number">-1</span>])</span><br><span class="line">    index = center.index(rear[<span class="number">-1</span>])</span><br><span class="line">    cur.left = rebuild(rear[:index], center[:index])</span><br><span class="line">    cur.right = rebuild(rear[index:<span class="number">-1</span>], center[index + <span class="number">1</span>:]) <span class="meta">#rear[index:-1]是到倒数第二个数</span></span><br><span class="line">    <span class="keyword">return</span> cur</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line">def pre_order(t):</span><br><span class="line">    <span class="keyword">if</span> t == None:</span><br><span class="line">        <span class="keyword">return</span></span><br><span class="line">    print(t.data)</span><br><span class="line">    pre_order(t.left)</span><br><span class="line">    pre_order(t.right)</span><br><span class="line"> </span><br><span class="line"> </span><br><span class="line"><span class="keyword">if</span> __name__ == <span class="string">&quot;__main__&quot;</span>:</span><br><span class="line">    rear = [<span class="string">&#x27;d&#x27;</span>,<span class="string">&#x27;a&#x27;</span>,<span class="string">&#x27;b&#x27;</span>,<span class="string">&#x27;e&#x27;</span>,<span class="string">&#x27;c&#x27;</span>]</span><br><span class="line">    center = [<span class="string">&#x27;d&#x27;</span>,<span class="string">&#x27;e&#x27;</span>,<span class="string">&#x27;b&#x27;</span>,<span class="string">&#x27;a&#x27;</span>,<span class="string">&#x27;c&#x27;</span>]</span><br><span class="line">    t = rebuild(rear, center)</span><br><span class="line">    pre_order(t)</span><br></pre></td></tr></table></figure>

<h2 id="二、-实验要求"><a href="#二、-实验要求" class="headerlink" title="二、 实验要求"></a><strong>二、</strong> <strong>实验要求</strong></h2><p>有如下二叉树：</p>
<p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072700.png" alt="二叉树"></p>
<p>程序代码给出了该二叉树的链式存储结构的建立、前序、中序、后序遍历的算法，同时也给出了查询“E”是否在二叉树里的代码。代码有三处错误，有标识，属于逻辑错误，对照书中的代码仔细分析后，请修改了在电脑里运行。</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">char</span> DataType;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">Node</span></span></span><br><span class="line"><span class="class"></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line"></span><br><span class="line">DataType data;<span class="comment">/*数据域*/</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> *<span class="title">leftChild</span>;</span><span class="comment">/*左子树指针*/</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">Node</span> *<span class="title">rightChild</span>;</span><span class="comment">/*右子树指针*/</span></span><br><span class="line"></span><br><span class="line">&#125;BiTreeNode;<span class="comment">/*结点的结构体定义*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*初始化创建二叉树的头结点*/</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Initiate</span><span class="params">(BiTreeNode **root)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">- root = (BiTreeNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(BiTreeNode));</span><br><span class="line"></span><br><span class="line">(*root)-&gt;leftChild = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">(*root)-&gt;rightChild = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Destroy</span><span class="params">(BiTreeNode **root)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>((*root) != <span class="literal">NULL</span> &amp;&amp; (*root)-&gt;leftChild != <span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">Destroy(&amp;(*root)-&gt;leftChild);</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>((*root) != <span class="literal">NULL</span> &amp;&amp; (*root)-&gt;rightChild != <span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">Destroy(&amp;(*root)-&gt;rightChild);</span><br><span class="line"></span><br><span class="line"><span class="built_in">free</span>(*root);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*若当前结点curr非空，在curr的左子树插入元素值为x的新结点*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*原curr所指结点的左子树成为新插入结点的左子树*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*若插入成功返回新插入结点的指针，否则返回空指针*/</span></span><br><span class="line"></span><br><span class="line"><span class="function">BiTreeNode *<span class="title">InsertLeftNode</span><span class="params">(BiTreeNode *curr, DataType x)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">BiTreeNode *s, *t;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(curr == <span class="literal">NULL</span>) <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">t = curr-&gt;leftChild;<span class="comment">/*保存原curr所指结点的左子树指针*/</span></span><br><span class="line"></span><br><span class="line">s = (BiTreeNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(BiTreeNode));</span><br><span class="line"></span><br><span class="line">s-&gt;data = x;</span><br><span class="line"></span><br><span class="line">s-&gt;leftChild = t;<span class="comment">/*新插入结点的左子树为原curr的左子树*/</span></span><br><span class="line"></span><br><span class="line">s-&gt;rightChild = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">curr-&gt;leftChild = s;<span class="comment">/*新结点成为curr的左子树*/</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">return</span> curr-&gt;leftChild;<span class="comment">/*返回新插入结点的指针*/</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*若当前结点curr非空，在curr的右子树插入元素值为x的新结点*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*原curr所指结点的右子树成为新插入结点的右子树*/</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*若插入成功返回新插入结点的指针，否则返回空指针*/</span></span><br><span class="line"></span><br><span class="line"><span class="function">BiTreeNode *<span class="title">InsertRightNode</span><span class="params">(BiTreeNode *curr, DataType x)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">BiTreeNode *s, *t;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(curr == <span class="literal">NULL</span>) <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">t = curr-&gt;rightChild;<span class="comment">/*保存原curr所指结点的右子树指针*/</span></span><br><span class="line"></span><br><span class="line">s = (BiTreeNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(BiTreeNode));</span><br><span class="line"></span><br><span class="line">s-&gt;data = x;</span><br><span class="line"></span><br><span class="line">s-&gt;rightChild = t;<span class="comment">/*新插入结点的右子树为原curr的右子树*/</span></span><br><span class="line"></span><br><span class="line">s-&gt;leftChild = <span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line">curr-&gt;rightChild = s;<span class="comment">/*新结点成为curr的右子树*/</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">return</span> curr-&gt;rightChild;<span class="comment">/*返回新插入结点的指针*/</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">PreOrder</span><span class="params">(BiTreeNode *t, <span class="keyword">void</span> visit(DataType item))</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"><span class="comment">//使用visit(item)函数前序遍历二叉树t</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(t != <span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">&#123;<span class="comment">//此小段有一处错误</span></span><br><span class="line"></span><br><span class="line">visit(t-&gt;data);</span><br><span class="line"></span><br><span class="line">PreOrder(t-&gt; rightChild, visit);</span><br><span class="line"></span><br><span class="line">PreOrder(t-&gt; leftChild, visit);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">InOrder</span><span class="params">(BiTreeNode *t, <span class="keyword">void</span> visit(DataType item))</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"><span class="comment">//使用visit(item)函数中序遍历二叉树t</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(t != <span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">&#123;<span class="comment">//此小段有一处错误</span></span><br><span class="line"></span><br><span class="line">InOrder(t-&gt;leftChild, visit);</span><br><span class="line"></span><br><span class="line">InOrder(t-&gt;rightChild, visit);</span><br><span class="line"></span><br><span class="line">visit(t-&gt;data);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">PostOrder</span><span class="params">(BiTreeNode *t, <span class="keyword">void</span> visit(DataType item))</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"><span class="comment">//使用visit(item)函数后序遍历二叉树t</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(t != <span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">&#123;<span class="comment">//此小段有一处错误</span></span><br><span class="line"></span><br><span class="line">visit(t-&gt;data);</span><br><span class="line"></span><br><span class="line">PostOrder(t-&gt;leftChild, visit);</span><br><span class="line"></span><br><span class="line">PostOrder(t-&gt;rightChild, visit);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">Visit</span><span class="params">(DataType item)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c &quot;</span>, item);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function">BiTreeNode *<span class="title">Search</span><span class="params">(BiTreeNode *root, DataType x)</span><span class="comment">//需找元素x是否在二叉树中</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">BiTreeNode *find=<span class="literal">NULL</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(root!=<span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(root-&gt;data==x)</span><br><span class="line"></span><br><span class="line">find=root;</span><br><span class="line"></span><br><span class="line"><span class="keyword">else</span></span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line">find=Search(root-&gt;leftChild,x);</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(find==<span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line">find=Search(root-&gt;rightChild,x);</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">return</span> find;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">(<span class="keyword">void</span>)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line">BiTreeNode *root, *p, *pp,*find;</span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> x=<span class="string">&#x27;E&#x27;</span>;</span><br><span class="line"></span><br><span class="line">Initiate(&amp;root);</span><br><span class="line"></span><br><span class="line">p = InsertLeftNode(root, <span class="string">&#x27;A&#x27;</span>);</span><br><span class="line"></span><br><span class="line">p = InsertLeftNode(p, <span class="string">&#x27;B&#x27;</span>);</span><br><span class="line"></span><br><span class="line">p = InsertLeftNode(p, <span class="string">&#x27;D&#x27;</span>);</span><br><span class="line"></span><br><span class="line">p = InsertRightNode(p, <span class="string">&#x27;G&#x27;</span>);</span><br><span class="line"></span><br><span class="line">p = InsertRightNode(root-&gt;leftChild, <span class="string">&#x27;C&#x27;</span>);</span><br><span class="line"></span><br><span class="line">pp = p;</span><br><span class="line"></span><br><span class="line">InsertLeftNode(p, <span class="string">&#x27;E&#x27;</span>);</span><br><span class="line"></span><br><span class="line">InsertRightNode(pp, <span class="string">&#x27;F&#x27;</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;前序遍历：&quot;</span>);</span><br><span class="line"></span><br><span class="line">PreOrder(root-&gt;leftChild, Visit);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\\n中序遍历：&quot;</span>);</span><br><span class="line"></span><br><span class="line">InOrder(root-&gt;leftChild, Visit);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\\n后序遍历：&quot;</span>);</span><br><span class="line"></span><br><span class="line">PostOrder(root-&gt;leftChild, Visit);</span><br><span class="line"></span><br><span class="line">find=Search(root,x);</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(find!=<span class="literal">NULL</span>)</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\\n数据元素%c在二叉树中 \\n&quot;</span>,x);</span><br><span class="line"></span><br><span class="line"><span class="keyword">else</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\\n数据元素%c不在二叉树中 \\n&quot;</span>,x);</span><br><span class="line"></span><br><span class="line">Destroy(&amp;root);</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="三、-实验任务："><a href="#三、-实验任务：" class="headerlink" title="三、 实验任务："></a><strong>三、</strong> <strong>实验任务：</strong></h2><p>1.改正程序错误。</p>
<p>2.编写二叉树的前序（或中序）的非递归遍历算法并进行测试。</p>
<p><img src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210321072712.png" alt="image-20210321072712755"></p>
<p>#include<stack></p>
<p>using namespace std;</p>
<p>stack&lt;BiTreeNode*&gt; s;</p>
<p>BiTreeNode *p;</p>
<p>s.push(p);</p>
<p>s.top();</p>
<p>s.pop();</p>
<p>s.empty()_</p>
<p>3.完成实验报告的撰写。</p>
<h2 id="实验六、图的遍历操作及应用"><a href="#实验六、图的遍历操作及应用" class="headerlink" title="实验六、图的遍历操作及应用"></a><strong>实验六、图的遍历操作及应用</strong></h2><ul>
<li><em><strong>一*、*实验目的*</strong></em></li>
</ul>
<p>掌握有向图和无向图的概念；掌握邻接矩阵和邻接链表建立图的存储结构；掌握DFS及BFS对图的遍历操作；了解图结构在人工智能、工程等领域的广泛应用。</p>
<p><strong>二、</strong> <em><strong>实验要求*</strong></em></p>
<p>采用邻接矩阵和邻接链表作为图的存储结构，完成有向图和无向图的DFS和BFS操作。本实验给出了示例程序，其中共有4处错误，错误段均有标识，属于逻辑错误。请认真理解程序，修改程序代码，并在电脑上调试运行。</p>
<p><strong>三、</strong> <em><strong>DFS和BFS 的基本思想*</strong></em></p>
<ul>
<li><em><strong>深度优先搜索法DFS的基本思想：</strong></em>*从图G中某个顶点Vo出发，首先访问Vo，然后选择一个与Vo相邻且没被访问过的顶点Vi访问，再从Vi出发选择一个与Vi相邻且没被访问过的顶点Vj访问，……依次继续。如果当前被访问过的顶点的所有邻接顶点都已被访问，则回退到已被访问的顶点序列中最后一个拥有未被访问的相邻顶点的顶点W，从W出发按同样方法向前遍历。直到图中所有的顶点都被访问。</li>
<li><em><strong>广度优先算法BFS的基本思想：</strong></em>*从图G中某个顶点Vo出发，首先访问Vo，然后访问与Vo相邻的所有未被访问过的顶点V1，V2，……，Vt；再依次访问与V1，V2，……，Vt相邻的起且未被访问过的的所有顶点。如此继续，直到访问完图中的所有顶点。</li>
</ul>
<p><img src="private/var/folders/rq/rhtpqfks4_3brk7ddz_g1qh80000gn/T/com.kingsoft.wpsoffice.mac/wps-tanzicai/ksohtml/wpsF7cE0U.png?lastModify=1605522401" alt="file:////private/var/folders/rq/rhtpqfks4_3brk7ddz_g1qh80000gn/T/com.kingsoft.wpsoffice.mac/wps-tanzicai/ksohtml/wpsF7cE0U.png?lastModify=1605522401"></p>
<p>四、</p>
<ul>
<li>示例程序</li>
<li>1.邻接矩阵作为存储结构的程序示例</li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;stdio.h&quot;</span></span></span><br><span class="line"></span><br><span class="line">\<span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;stdlib.h&quot;</span></span></span><br><span class="line"></span><br><span class="line">\<span class="meta">#<span class="meta-keyword">define</span> MaxVertexNum 100 <span class="comment">//定义最大顶点数</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> vexs[MaxVertexNum]; <span class="comment">//顶点表</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> edges**[MaxVertexNum](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**; //邻接矩阵，可看作边表</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,e; <span class="comment">//图中的顶点数n和边数e</span></span><br><span class="line"></span><br><span class="line">&#125;MGraph; <span class="comment">//用邻接矩阵表示的图的类型</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//=========建立邻接矩阵=======</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">void</span> CreatMGraph(MGraph *G)</span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i,j,k;</span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> a;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input VertexNum(n) and EdgesNum(e): &quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%d,%d&quot;</span>,&amp;G-&gt;n,&amp;G-&gt;e); <span class="comment">//输入顶点数和边数</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>,&amp;a);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input Vertex string:&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>,&amp;a);</span><br><span class="line"></span><br><span class="line">G-&gt;vexs[i]=a; <span class="comment">//读入顶点信息，建立顶点表</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(j=<span class="number">0</span>;j&lt;G-&gt;n;j++)</span><br><span class="line"></span><br><span class="line">G-&gt;edges**[i](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=0; //初始化邻接矩阵</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input edges,Creat Adjacency Matrix\n&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(k=<span class="number">0</span>;k&lt;G-&gt;e;k++) &#123; <span class="comment">//读入e条边，建立邻接矩阵</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;i,&amp;j); <span class="comment">//输入边（Vi，Vj）的顶点序号</span></span><br><span class="line"></span><br><span class="line">G-&gt;edges**[i](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=1;</span></span><br><span class="line"></span><br><span class="line">G-&gt;edges**[j](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**=1; //若为无向图，矩阵为对称矩阵；若建立有向图，去掉该条语句</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//=========定义标志向量，为全局变量=======</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="keyword">enum</span>&#123;FALSE,TRUE&#125; Boolean;</span><br><span class="line"></span><br><span class="line">Boolean visited[MaxVertexNum];</span><br><span class="line"></span><br><span class="line"><span class="comment">//========DFS：深度优先遍历的递归算法======</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">void</span> DFSM(MGraph *G,<span class="keyword">int</span> i)</span><br><span class="line"></span><br><span class="line">&#123; <span class="comment">//以Vi为出发点对邻接矩阵表示的图G进行DFS搜索，邻接矩阵是0，1矩阵</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> j;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;vexs[i]); <span class="comment">//访问顶点Vi</span></span><br><span class="line"></span><br><span class="line">visited[i]=TRUE; <span class="comment">//置已访问标志</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(j=<span class="number">0</span>;j&lt;G-&gt;n;j++) <span class="comment">//依次搜索Vi的邻接点</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(G-&gt;edges**[i](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**==1 &amp;&amp; ! visited[j])</span></span><br><span class="line"></span><br><span class="line">DFSM(G,j); <span class="comment">//（Vi，Vj）∈E，且Vj未访问过，故Vj为新出发点</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="keyword">void</span> DFS(MGraph *G)</span><br><span class="line"></span><br><span class="line">&#123; <span class="comment">//此段代码有一处错误</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i;</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">visited[i]=FALSE; <span class="comment">//标志向量初始化</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(!visited[i]) <span class="comment">//Vi未访问过</span></span><br><span class="line"></span><br><span class="line">DFS(G,i); <span class="comment">//以Vi为源点开始DFS搜索</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//===========BFS：广度优先遍历=======</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">void</span> BFS(MGraph *G,<span class="keyword">int</span> k)</span><br><span class="line"></span><br><span class="line">&#123; <span class="comment">//以Vk为源点对用邻接矩阵表示的图G进行广度优先搜索</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i,j,f=<span class="number">0</span>,r=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> cq[MaxVertexNum]; <span class="comment">//定义队列</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">visited[i]=FALSE; <span class="comment">//标志向量初始化</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;=G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">cq[i]=<span class="number">-1</span>; <span class="comment">//队列初始化</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;vexs[k]); <span class="comment">//访问源点Vk</span></span><br><span class="line"></span><br><span class="line">visited[k]=TRUE;</span><br><span class="line"></span><br><span class="line">cq[r]=k; <span class="comment">//Vk已访问，将其入队。注意，实际上是将其序号入队</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(cq[f]!=<span class="number">-1</span>) &#123; <span class="comment">//队非空则执行</span></span><br><span class="line"></span><br><span class="line">i=cq[f]; f=f+<span class="number">1</span>; <span class="comment">//Vf出队</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(j=<span class="number">0</span>;j&lt;G-&gt;n;j++) <span class="comment">//依次Vi的邻接点Vj</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(G-&gt;edges**[i](notion:<span class="comment">//www.notion.so/afc75248d48d4c3baadfce4b9c10a03d#)**==1 &amp;&amp; !visited[j]) &#123; //Vj未访问 以下三行代码有一处错误</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;vexs[j]); <span class="comment">//访问Vj</span></span><br><span class="line"></span><br><span class="line">visited[j]=FALSE; r=r+<span class="number">1</span>; cq[r]=j; <span class="comment">//访问过Vj入队</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//==========main=====</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">void</span> main()</span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line">MGraph *G;</span><br><span class="line"></span><br><span class="line">G=(MGraph *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(MGraph)); <span class="comment">//为图G申请内存空间</span></span><br><span class="line"></span><br><span class="line">CreatMGraph(G); <span class="comment">//建立邻接矩阵</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Print Graph DFS: &quot;</span>);</span><br><span class="line"></span><br><span class="line">DFS(G); <span class="comment">//深度优先遍历</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Print Graph BFS: &quot;</span>);</span><br><span class="line"></span><br><span class="line">BFS(G,<span class="number">3</span>); <span class="comment">//以序号为3的顶点开始广度优先遍历</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);&#125;</span><br></pre></td></tr></table></figure>



<ul>
<li><em><strong>执行顺序：*</strong></em></li>
</ul>
<figure class="highlight plaintext"><figcaption><span>VertexNum(n) and EdgesNum(e): 8，9</span></figcaption><table><tr><td class="code"><pre><span class="line">Input Vertex string: 01234567</span><br><span class="line"></span><br><span class="line">Input edges,Creat Adjacency Matrix</span><br><span class="line"></span><br><span class="line">0 1</span><br><span class="line"></span><br><span class="line">0 2</span><br><span class="line"></span><br><span class="line">1 3</span><br><span class="line"></span><br><span class="line">1 4</span><br><span class="line"></span><br><span class="line">2 5</span><br><span class="line"></span><br><span class="line">2 6</span><br><span class="line"></span><br><span class="line">3 7</span><br><span class="line"></span><br><span class="line">4 7</span><br><span class="line"></span><br><span class="line">5 6</span><br><span class="line"></span><br><span class="line">Print Graph DFS: 01374256</span><br><span class="line"></span><br><span class="line">Print Graph BFS: 31704256</span><br></pre></td></tr></table></figure>

<ul>
<li><em><strong>2.*邻接链表作为存储结构程序示例*</strong></em></li>
</ul>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">\<span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;stdio.h&quot;</span></span></span><br><span class="line"></span><br><span class="line">\<span class="meta">#<span class="meta-keyword">include</span><span class="meta-string">&quot;stdlib.h&quot;</span></span></span><br><span class="line"></span><br><span class="line">\<span class="meta">#<span class="meta-keyword">define</span> MaxVertexNum 50 <span class="comment">//定义最大顶点数</span></span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span> <span class="comment">//边表结点</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> adjvex; <span class="comment">//邻接点域</span></span><br><span class="line"></span><br><span class="line"><span class="class"><span class="keyword">struct</span> <span class="title">node</span> *<span class="title">next</span>;</span> <span class="comment">//链域</span></span><br><span class="line"></span><br><span class="line">&#125;EdgeNode;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">vnode</span>&#123;</span> <span class="comment">//顶点表结点</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> vertex; <span class="comment">//顶点域</span></span><br><span class="line"></span><br><span class="line">EdgeNode *firstedge; <span class="comment">//边表头指针</span></span><br><span class="line"></span><br><span class="line">&#125;VertexNode;</span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> VertexNode AdjList[MaxVertexNum]; <span class="comment">//AdjList是邻接表类型</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> &#123;</span></span><br><span class="line"></span><br><span class="line">AdjList adjlist; <span class="comment">//邻接表</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> n,e; <span class="comment">//图中当前顶点数和边数</span></span><br><span class="line"></span><br><span class="line">&#125; ALGraph; <span class="comment">//图类型</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//=========建立图的邻接表=======</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">CreatALGraph</span><span class="params">(ALGraph *G)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i,j,k;</span><br><span class="line"></span><br><span class="line"><span class="keyword">char</span> a;</span><br><span class="line"></span><br><span class="line">EdgeNode *s; <span class="comment">//定义边表结点</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input VertexNum(n) and EdgesNum(e): &quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%d,%d&quot;</span>,&amp;G-&gt;n,&amp;G-&gt;e); <span class="comment">//读入顶点数和边数</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>,&amp;a);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input Vertex string:&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++) <span class="comment">//建立顶点表</span></span><br><span class="line"></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%c&quot;</span>,&amp;a);</span><br><span class="line"></span><br><span class="line">G-&gt;adjlist[i].vertex=a; <span class="comment">//读入顶点信息</span></span><br><span class="line"></span><br><span class="line">G-&gt;adjlist[i].firstedge=<span class="literal">NULL</span>; <span class="comment">//边表置为空表</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Input edges,Creat Adjacency List\n&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(k=<span class="number">0</span>;k&lt;G-&gt;e;k++) &#123; <span class="comment">//建立边表</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">scanf</span>(<span class="string">&quot;%d%d&quot;</span>,&amp;i,&amp;j); <span class="comment">//读入边（Vi，Vj）的顶点对序号</span></span><br><span class="line"></span><br><span class="line">s=(EdgeNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(EdgeNode)); <span class="comment">//生成边表结点</span></span><br><span class="line"></span><br><span class="line">s-&gt;adjvex=j; <span class="comment">//邻接点序号为j</span></span><br><span class="line"></span><br><span class="line">s-&gt;next=G-&gt;adjlist[i].firstedge;</span><br><span class="line"></span><br><span class="line">G-&gt;adjlist[i].firstedge=s; <span class="comment">//将新结点*S插入顶点Vi的边表头部</span></span><br><span class="line"></span><br><span class="line">s=(EdgeNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(EdgeNode));</span><br><span class="line"></span><br><span class="line">s-&gt;adjvex=i; <span class="comment">//邻接点序号为i</span></span><br><span class="line"></span><br><span class="line">s-&gt;next=G-&gt;adjlist[j].firstedge;</span><br><span class="line"></span><br><span class="line">G-&gt;adjlist[j].firstedge=s; <span class="comment">//将新结点*S插入顶点Vj的边表头部</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//=========定义标志向量，为全局变量=======</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">enum</span>&#123;</span>FALSE,TRUE&#125; Boolean;</span><br><span class="line"></span><br><span class="line">Boolean visited[MaxVertexNum];</span><br><span class="line"></span><br><span class="line"><span class="comment">//========DFS：深度优先遍历的递归算法======</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">DFSM</span><span class="params">(ALGraph *G,<span class="keyword">int</span> i)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123; <span class="comment">//以Vi为出发点对邻接链表表示的图G进行DFS搜索</span></span><br><span class="line"></span><br><span class="line">EdgeNode *p;</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;adjlist[i].vertex); <span class="comment">//访问顶点Vi</span></span><br><span class="line"></span><br><span class="line">visited[i]=TRUE; <span class="comment">//标记Vi已访问</span></span><br><span class="line"></span><br><span class="line">p=G-&gt;adjlist[i].firstedge; <span class="comment">//取Vi边表的头指针</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(p) &#123; <span class="comment">//依次搜索Vi的邻接点Vj，这里j=p-&gt;adjvex</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//以下3行代码有一处错误</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(! visited[p-&gt;adjvex]) <span class="comment">//若Vj尚未被访问</span></span><br><span class="line"></span><br><span class="line">DFS(G,p-&gt;adjvex); <span class="comment">//则以Vj为出发点向纵深搜索</span></span><br><span class="line"></span><br><span class="line">p=p-&gt;next; <span class="comment">//找Vi的下一个邻接点</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">DFS</span><span class="params">(ALGraph *G)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i;</span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">visited[i]=FALSE; <span class="comment">//标志向量初始化</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(!visited[i]) <span class="comment">//Vi未访问过</span></span><br><span class="line"></span><br><span class="line">DFSM(G,i); <span class="comment">//以Vi为源点开始DFS搜索</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//==========BFS：广度优先遍历=========</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">BFS</span><span class="params">(ALGraph *G,<span class="keyword">int</span> k)</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123; <span class="comment">//以Vk为源点对用邻接链表表示的图G进行广度优先搜索</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i,f=<span class="number">0</span>,r=<span class="number">0</span>;</span><br><span class="line"></span><br><span class="line">EdgeNode *p;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> cq[MaxVertexNum]; <span class="comment">//定义FIFO队列</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">visited[i]=FALSE; <span class="comment">//标志向量初始化</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">for</span>(i=<span class="number">0</span>;i&lt;=G-&gt;n;i++)</span><br><span class="line"></span><br><span class="line">cq[i]=<span class="number">-1</span>; <span class="comment">//初始化标志向量</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;adjlist[k].vertex); <span class="comment">//访问源点Vk</span></span><br><span class="line"></span><br><span class="line">visited[k]=TRUE;</span><br><span class="line"></span><br><span class="line">cq[r]=k; <span class="comment">//Vk已访问，将其入队。注意，实际上是将其序号入队</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(cq[f]!=<span class="number">-1</span>)</span><br><span class="line"></span><br><span class="line">&#123; <span class="comment">//队列非空则执行</span></span><br><span class="line"></span><br><span class="line">i=cq[f]; f=f+<span class="number">1</span>; <span class="comment">//Vi出队</span></span><br><span class="line"></span><br><span class="line">p=G-&gt;adjlist[i].firstedge; <span class="comment">//取Vi的边表头指针</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">while</span>(p)</span><br><span class="line"></span><br><span class="line">&#123; <span class="comment">//依次搜索Vi的邻接点Vj（令p-&gt;adjvex=j）</span></span><br><span class="line"></span><br><span class="line"><span class="keyword">if</span>(!visited[p-&gt;adjvex]) &#123; <span class="comment">//若Vj未访问过</span></span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%c&quot;</span>,G-&gt;adjlist[p-&gt;adjvex].vertex); <span class="comment">//访问Vj</span></span><br><span class="line"></span><br><span class="line">visited[p-&gt;adjvex]=TRUE;</span><br><span class="line"></span><br><span class="line"><span class="comment">//以下3行代码有一处错误</span></span><br><span class="line"></span><br><span class="line">r=r+<span class="number">1</span>; cq[r]=p-&gt;adjvex; <span class="comment">//访问过的Vj入队</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">p=p-&gt;next-&gt;next; <span class="comment">//找Vi的下一个邻接点</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line">&#125;<span class="comment">//endwhile</span></span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//==========主函数===========</span></span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"></span><br><span class="line"><span class="keyword">int</span> i;</span><br><span class="line"></span><br><span class="line">ALGraph *G;</span><br><span class="line"></span><br><span class="line">G=(ALGraph *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(ALGraph));</span><br><span class="line"></span><br><span class="line">CreatALGraph(G);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Print Graph DFS: &quot;</span>);</span><br><span class="line"></span><br><span class="line">DFS(G);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;Print Graph BFS: &quot;</span>);</span><br><span class="line"></span><br><span class="line">BFS(G,<span class="number">3</span>);</span><br><span class="line"></span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>



<ul>
<li><em><strong>执行顺序：*</strong></em></li>
</ul>
<figure class="highlight plaintext"><table><tr><td class="code"><pre><span class="line">Input VertexNum(n) and EdgesNum(e): 8，9</span><br><span class="line"></span><br><span class="line">Input Vertex string: 01234567</span><br><span class="line"></span><br><span class="line">Input edges,Creat Adjacency List</span><br><span class="line"></span><br><span class="line">0 1</span><br><span class="line"></span><br><span class="line">0 2</span><br><span class="line"></span><br><span class="line">1 3</span><br><span class="line"></span><br><span class="line">1 4</span><br><span class="line"></span><br><span class="line">2 5</span><br><span class="line"></span><br><span class="line">2 6</span><br><span class="line"></span><br><span class="line">3 7</span><br><span class="line"></span><br><span class="line">4 7</span><br><span class="line"></span><br><span class="line">5 6</span><br><span class="line"></span><br><span class="line">Print Graph DFS: 02651473</span><br><span class="line"></span><br><span class="line">Print Graph BFS: 37140265</span><br></pre></td></tr></table></figure>



<p><strong>二、</strong> <em><strong>实验任务*</strong></em></p>
<p>\1. 改正程序中的错误并调试通过，测试并完成实验报告的撰写。</p>
<p>\2. 选做题，编写程序输出该无向网络的最小生成树以及该最小生成树的所有边。</p>
<h2 id="实验七、查找算法的实现"><a href="#实验七、查找算法的实现" class="headerlink" title="实验七、查找算法的实现"></a>实验七、查找算法的实现</h2><p><strong>一、实验目的</strong></p>
<p>掌握<strong>顺序和二分查找算法</strong>的基本思想及其实现方法。</p>
<p><strong>二、实验要求</strong></p>
<p>问题描述：对给定的任意数组（设其长度为n），分别用顺序和二分查找方法在此数组中查找与给定值k相等的元素。</p>
<p><strong>顺序查找基本思想：</strong>从查找表的一端开始，逐个将记录的关键字值和给定值进行比较，如果某个记录的关键字值和给定值相等，则称查找成功；否则，说明查找表中不存在关键字值为给定值的记录，则称查找失败。</p>
<p><strong>二分查找基本思想：</strong>先取查找表的中间位置的关键字值与给定关键字值作比较，若它们的值相等，则查找成功；如果给定值比该记录的关键字值大，说明要查找的记录一定在查找表的后半部分，则在查找表的后半部分继续使用折半查找；若给定值比该记录的关键字值小，说明要查找的记录一定在查找表的前半部分，则在查找表的前半部分继续使用折半查找。…直到查找成功，或者直到确定查找表中没有待查找的记录为止，即查找失败。</p>
<p><strong>两者比较：</strong></p>
<p>（1）顺序查找的查找效率很低；但是对于待查记录的存储结构没有任何要求，既适用于顺序存储，又适用于链式存储；当待查表中的记录个数较少时，采用顺序查找法较好。</p>
<p>（2）二分查找的平均查找长度较小，查找速度快；但它只能用于顺序存储，不能用于链式存储；且要求表中的记录是有序的。对于不常变动的有序表，采用折半查找法是较为理想的。</p>
<p><strong>三、算法思想与算法描述</strong></p>
<p>1、顺序查找，在顺序表R[0..n-1]中查找关键字为k的记录，成功时返回找到的记录位置，失败时返回-1，具体的算法如下所示：</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">SeqSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"><span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">while</span>(i&lt;n&amp;&amp;R[i].key!=k)</span><br><span class="line">&#123;</span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,R[i].key);</span><br><span class="line">i++;</span><br><span class="line"></span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">if</span>(i&gt;=n)</span><br><span class="line"><span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line"><span class="keyword">else</span></span><br><span class="line">&#123;</span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;%d&quot;</span>,R[i].key);</span><br><span class="line"><span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>程序代码</strong></p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> KeyType int</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_SIZE 10</span></span><br><span class="line"><span class="comment">//顺序表结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> oder;</span><br><span class="line">    KeyType key;</span><br><span class="line">&#125;SeqList;</span><br><span class="line"><span class="comment">//顺序查找函数</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">SeqSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n&amp;&amp;R[i].key!=k)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//printf(&quot;%d:%d\\n&quot;,i,R[i].key);</span></span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(i &gt; n)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d！&quot;</span>,R[i].key);</span><br><span class="line">        <span class="keyword">return</span> i;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">		<span class="comment">//初始化待查找数据</span></span><br><span class="line">    SeqList source[]=&#123;&#123;<span class="number">0</span>,<span class="number">9</span>&#125;,&#123;<span class="number">1</span>,<span class="number">13</span>&#125;,&#123;<span class="number">2</span>,<span class="number">15</span>&#125;,&#123;<span class="number">3</span>,<span class="number">7</span>&#125;,&#123;<span class="number">4</span>,<span class="number">45</span>&#125;,&#123;<span class="number">5</span>,<span class="number">32</span>&#125;,&#123;<span class="number">6</span>,<span class="number">56</span>&#125;,&#123;<span class="number">7</span>,<span class="number">89</span>&#125;,&#123;<span class="number">8</span>,<span class="number">60</span>&#125;,&#123;<span class="number">9</span>,<span class="number">36</span>&#125;&#125;;</span><br><span class="line">    <span class="comment">//查找的数据</span></span><br><span class="line">		<span class="keyword">int</span> finder;</span><br><span class="line">		<span class="comment">//返回的下标</span></span><br><span class="line">    <span class="keyword">int</span> result=<span class="number">-1</span>;</span><br><span class="line">		<span class="comment">//查找开始</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;程序开始***************************\\n请输入查找内容：&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;finder);</span><br><span class="line">		<span class="comment">//返回查找内容 -1：未找到 否则返回下标志</span></span><br><span class="line">    result= SeqSearch(source,<span class="number">9</span>,finder);</span><br><span class="line">    <span class="keyword">if</span> (result == <span class="number">-1</span>)<span class="built_in">printf</span>(<span class="string">&quot;未查找到相关信息&quot;</span>);</span><br><span class="line">    <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;所查找元素下标值为%d&quot;</span>,result);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p>2、二分查找，在有序表R[0..n-1]中进行二分查找，成功时返回记录的位置，失败时返回-1，具体的算法如下：</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BinSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line"><span class="keyword">int</span> low=<span class="number">0</span>,high=n<span class="number">-1</span>,mid,count=<span class="number">0</span>;</span><br><span class="line"><span class="keyword">while</span>(low&lt;=high)</span><br><span class="line">&#123;</span><br><span class="line">mid=(low+high)/<span class="number">2</span>;</span><br><span class="line"><span class="built_in">printf</span>(<span class="string">&quot;第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n &quot;</span>,++count,low,high,mid,R[mid].key);</span><br><span class="line"><span class="keyword">if</span>(R[mid].key==k)</span><br><span class="line"><span class="keyword">return</span> mid;</span><br><span class="line"><span class="keyword">if</span>(R[mid].key&gt;k)</span><br><span class="line">high=mid<span class="number">-1</span>;</span><br><span class="line"><span class="keyword">else</span></span><br><span class="line">low=mid+<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> KeyType int</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_SIZE 10</span></span><br><span class="line"><span class="comment">//顺序表结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span>&#123;</span></span><br><span class="line">    <span class="keyword">int</span> oder;</span><br><span class="line">    KeyType key;</span><br><span class="line">&#125;SeqList;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BinSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> low=<span class="number">0</span>,high=n<span class="number">-1</span>,mid,count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(low&lt;=high)</span><br><span class="line">    &#123;</span><br><span class="line">        mid=(low+high)/<span class="number">2</span>;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n &quot;</span>,++count,low,high,mid,R[mid].key);</span><br><span class="line">        <span class="keyword">if</span>(R[mid].key==k)</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        <span class="keyword">if</span>(R[mid].key&gt;k)</span><br><span class="line">            high=mid<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            low=mid+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="comment">//初始化待查找数据</span></span><br><span class="line">    SeqList source[]=&#123;&#123;<span class="number">0</span>,<span class="number">5</span>&#125;,&#123;<span class="number">1</span>,<span class="number">7</span>&#125;,&#123;<span class="number">2</span>,<span class="number">9</span>&#125;,&#123;<span class="number">3</span>,<span class="number">12</span>&#125;,&#123;<span class="number">4</span>,<span class="number">15</span>&#125;,&#123;<span class="number">5</span>,<span class="number">18</span>&#125;,&#123;<span class="number">6</span>,<span class="number">20</span>&#125;,&#123;<span class="number">7</span>,<span class="number">22</span>&#125;,&#123;<span class="number">8</span>,<span class="number">25</span>&#125;,&#123;<span class="number">9</span>,<span class="number">30</span>&#125;,&#123;<span class="number">10</span>,<span class="number">100</span>&#125;&#125;;</span><br><span class="line">    <span class="comment">//查找的数据</span></span><br><span class="line">    <span class="keyword">int</span> finder;</span><br><span class="line">    <span class="comment">//返回的下标</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;*********************程序开始***************************\\n&quot;</span>);</span><br><span class="line">    <span class="keyword">int</span> result=<span class="number">-1</span>;</span><br><span class="line">    <span class="comment">//查找开始</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请输入查找内容：&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;finder);</span><br><span class="line">    <span class="keyword">while</span> (finder != <span class="string">&#x27;-1&#x27;</span>)&#123;</span><br><span class="line">        <span class="comment">//返回查找内容 -1：未找到 否则返回下标志</span></span><br><span class="line">        result= BinSearch(source,<span class="number">10</span>,finder);</span><br><span class="line">        <span class="keyword">if</span> (result == <span class="number">-1</span>)<span class="built_in">printf</span>(<span class="string">&quot;未查找到相关信息\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">else</span> <span class="built_in">printf</span>(<span class="string">&quot;所查找元素下标值为%d\\n&quot;</span>,result);</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;请输入查找内容：&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;finder);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="C方式实现"><a href="#C方式实现" class="headerlink" title="C方式实现"></a>C方式实现</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line">#include &lt;stdio.h&gt;</span><br><span class="line">#define KeyType <span class="keyword">int</span></span><br><span class="line">#define MAX_SIZE <span class="number">10</span></span><br><span class="line"><span class="comment">//顺序表结构体</span></span><br><span class="line">typedef struct&#123;</span><br><span class="line">    <span class="keyword">int</span> oder;</span><br><span class="line">    KeyType key;</span><br><span class="line">&#125;SeqList;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 顺序查找</span></span><br><span class="line"><span class="comment"> * R[] 数组 待查找数据组</span></span><br><span class="line"><span class="comment"> * n int 待查找数据长度</span></span><br><span class="line"><span class="comment"> * k KeyType查找数据</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">SeqSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;=n&amp;&amp;R[i].key!=k)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//printf(&quot;%d:%d\\n&quot;,i,R[i].key);</span></span><br><span class="line">        i++;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>(i &gt; n)</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        printf(<span class="string">&quot;%d！&quot;</span>,R[i].key);</span><br><span class="line">        <span class="keyword">return</span> i;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 折半方查找</span></span><br><span class="line"><span class="comment"> * R[] 数组 待查找数据组</span></span><br><span class="line"><span class="comment"> * n int 待查找数据长度</span></span><br><span class="line"><span class="comment"> * k KeyType查找数据</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">BinSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> low=<span class="number">0</span>,high=n-<span class="number">1</span>,mid,count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span>(low&lt;=high)</span><br><span class="line">    &#123;</span><br><span class="line">        mid=(low+high)/<span class="number">2</span>;</span><br><span class="line">        printf(<span class="string">&quot;第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n &quot;</span>,++count,low,high,mid,R[mid].key);</span><br><span class="line">        <span class="keyword">if</span>(R[mid].key==k)</span><br><span class="line">            <span class="keyword">return</span> mid;</span><br><span class="line">        <span class="keyword">if</span>(R[mid].key&gt;k)</span><br><span class="line">            high=mid-<span class="number">1</span>;</span><br><span class="line">        <span class="keyword">else</span></span><br><span class="line">            low=mid+<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment"> * 插值查找</span></span><br><span class="line"><span class="comment"> * R[] 数组 待查找数据组</span></span><br><span class="line"><span class="comment"> * n int 待查找数据长度</span></span><br><span class="line"><span class="comment"> * k KeyType查找数据</span></span><br><span class="line"><span class="comment"> * */</span></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">interpolationSearch</span><span class="params">(SeqList R[],<span class="keyword">int</span> n,KeyType k)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> low=<span class="number">0</span>,high=n-<span class="number">1</span>,mid,count=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">while</span> (low &lt; high) &#123;</span><br><span class="line">        mid = low + (high - low) * (k - R[low].key) / (R[high].key - R[low].key);</span><br><span class="line">        printf(<span class="string">&quot;第%d次查找：在[ %d ,%d]中找到元素R[%d]:%d\\n &quot;</span>,++count,low,high,mid,R[mid].key);</span><br><span class="line">        <span class="comment">// mid = (high + low) / 2;// 折半下标</span></span><br><span class="line">        <span class="keyword">if</span> (k &gt; R[mid].key) &#123;</span><br><span class="line">            low = mid + <span class="number">1</span>; <span class="comment">// 关键字比 折半值 大，则最小下标 调成 折半下标的下一位</span></span><br><span class="line">        &#125; <span class="keyword">else</span> <span class="keyword">if</span> (k &lt; R[mid].key) &#123;</span><br><span class="line">            high = mid - <span class="number">1</span>;<span class="comment">// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位</span></span><br><span class="line">        &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">            <span class="keyword">return</span> mid; <span class="comment">// 当 key == a[mid] 返回 折半下标</span></span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span> </span>&#123;</span><br><span class="line">    <span class="comment">//初始化待查找数据</span></span><br><span class="line">    SeqList source1[]=&#123;&#123;<span class="number">0</span>,<span class="number">9</span>&#125;,&#123;<span class="number">1</span>,<span class="number">13</span>&#125;,&#123;<span class="number">2</span>,<span class="number">15</span>&#125;,&#123;<span class="number">3</span>,<span class="number">7</span>&#125;,&#123;<span class="number">4</span>,<span class="number">45</span>&#125;,&#123;<span class="number">5</span>,<span class="number">32</span>&#125;,&#123;<span class="number">6</span>,<span class="number">56</span>&#125;,&#123;<span class="number">7</span>,<span class="number">89</span>&#125;,&#123;<span class="number">8</span>,<span class="number">60</span>&#125;,&#123;<span class="number">9</span>,<span class="number">36</span>&#125;&#125;;</span><br><span class="line">    SeqList source2[]=&#123;&#123;<span class="number">0</span>,<span class="number">5</span>&#125;,&#123;<span class="number">1</span>,<span class="number">7</span>&#125;,&#123;<span class="number">2</span>,<span class="number">9</span>&#125;,&#123;<span class="number">3</span>,<span class="number">12</span>&#125;,&#123;<span class="number">4</span>,<span class="number">15</span>&#125;,&#123;<span class="number">5</span>,<span class="number">18</span>&#125;,&#123;<span class="number">6</span>,<span class="number">20</span>&#125;,&#123;<span class="number">7</span>,<span class="number">22</span>&#125;,&#123;<span class="number">8</span>,<span class="number">25</span>&#125;,&#123;<span class="number">9</span>,<span class="number">30</span>&#125;,&#123;<span class="number">10</span>,<span class="number">100</span>&#125;&#125;;</span><br><span class="line">    SeqList* source;</span><br><span class="line">    <span class="comment">//查找的数据</span></span><br><span class="line">    <span class="keyword">int</span> finder;</span><br><span class="line">    <span class="comment">//数据大小</span></span><br><span class="line">    <span class="keyword">int</span> size;</span><br><span class="line">    <span class="comment">//查找方式</span></span><br><span class="line">    <span class="keyword">int</span> way;</span><br><span class="line">    <span class="comment">//查找数据选择</span></span><br><span class="line">    <span class="keyword">int</span> data;</span><br><span class="line">    <span class="comment">//返回的下标</span></span><br><span class="line">    printf(<span class="string">&quot;程序开始***************************\\n&quot;</span>);</span><br><span class="line">    <span class="keyword">int</span> result=-<span class="number">1</span>;</span><br><span class="line">    <span class="comment">//查找开始</span></span><br><span class="line">    printf(<span class="string">&quot;请输入查找内容：&quot;</span>);</span><br><span class="line">    scanf(<span class="string">&quot;%d&quot;</span>,&amp;finder);</span><br><span class="line">    printf(<span class="string">&quot;请选择查找方式：\\n1:顺序查找\\n2:折半查找\\n3:插值查找&quot;</span>);</span><br><span class="line">    scanf(<span class="string">&quot;%d&quot;</span>,&amp;way);</span><br><span class="line">    printf(<span class="string">&quot;请选择待查找数组&quot;</span>);</span><br><span class="line">    scanf(<span class="string">&quot;%d&quot;</span>,&amp;data);</span><br><span class="line">    <span class="keyword">if</span> (data == <span class="number">1</span>)&#123;</span><br><span class="line">        source = source1;</span><br><span class="line">        size=<span class="number">9</span>;</span><br><span class="line">    &#125;<span class="keyword">else</span> <span class="keyword">if</span> (data ==<span class="number">2</span>)&#123;</span><br><span class="line">        source = source2;</span><br><span class="line">        size = <span class="number">10</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">while</span> (finder != <span class="string">&#x27;-1&#x27;</span>)&#123;</span><br><span class="line">        <span class="comment">//返回查找内容 -1：未找到 否则返回下标志</span></span><br><span class="line">        <span class="keyword">switch</span> (way) &#123;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">1</span>:result= SeqSearch(source,size,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">2</span>:result= BinSearch(source,size,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">3</span>:result= interpolationSearch(source,size,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">default</span>:printf(<span class="string">&quot;输入错误,程序结束&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (result == -<span class="number">1</span>)printf(<span class="string">&quot;未查找到相关信息\\n&quot;</span>);</span><br><span class="line">        <span class="keyword">else</span> printf(<span class="string">&quot;所查找元素下标值为%d\\n&quot;</span>,result);</span><br><span class="line">        printf(<span class="string">&quot;请输入查找内容：&quot;</span>);</span><br><span class="line">        scanf(<span class="string">&quot;%d&quot;</span>,&amp;finder);</span><br><span class="line">        printf(<span class="string">&quot;请选择查找方式：\\n1:顺序查找\\n2:折半查找\\n3:插值查找&quot;</span>);</span><br><span class="line">        scanf(<span class="string">&quot;%d&quot;</span>,&amp;way);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="Java方法实现"><a href="#Java方法实现" class="headerlink" title="Java方法实现"></a>Java方法实现</h3><figure class="highlight java"><table><tr><td class="code"><pre><span class="line"><span class="keyword">package</span> com.finder.oder;</span><br><span class="line"></span><br><span class="line"><span class="keyword">import</span> java.util.Scanner;</span><br><span class="line"></span><br><span class="line"><span class="keyword">public</span> <span class="class"><span class="keyword">class</span> <span class="title">Main</span></span>&#123;</span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">void</span> <span class="title">main</span><span class="params">(String args[])</span></span>&#123;</span><br><span class="line">        <span class="keyword">int</span>[] data = &#123;<span class="number">9</span>,<span class="number">13</span>,<span class="number">15</span>,<span class="number">7</span>,<span class="number">45</span>,<span class="number">32</span>,<span class="number">56</span>,<span class="number">89</span>,<span class="number">60</span>,<span class="number">36</span>&#125;;</span><br><span class="line">        <span class="keyword">int</span> finder;</span><br><span class="line">        <span class="keyword">int</span> way;</span><br><span class="line">        <span class="keyword">int</span> result=-<span class="number">1</span>;</span><br><span class="line">        System.out.println(<span class="string">&quot;请输入要查找的数据（int）&quot;</span>);</span><br><span class="line">        Scanner input = <span class="keyword">new</span> Scanner(System.in);</span><br><span class="line">        finder = input.nextInt();</span><br><span class="line">        way = input.nextInt();</span><br><span class="line">        System.out.println(<span class="string">&quot;请选择查找方法\\n1:顺序查找\\n2:优化顺序查找\\n3：折半查找\\n4.插值查找&quot;</span>);</span><br><span class="line">        <span class="keyword">switch</span> (way)&#123;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">1</span>:result = sequentialSearch(data,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">2</span>:result = sequentialSearch2(data,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">3</span>:result = binarySearch(data,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">case</span> <span class="number">4</span>:result = interpolationSearch(data,finder);<span class="keyword">break</span>;</span><br><span class="line">            <span class="keyword">default</span>:System.out.println(<span class="string">&quot;输入错误，程序结束&quot;</span>);</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (result != -<span class="number">1</span>)System.out.println(<span class="string">&quot;下标为&quot;</span>+result);</span><br><span class="line">				<span class="keyword">else</span> System.out.println(<span class="string">&quot;未查找到此数据&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 顺序查找</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key 待查找关键字</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 关键字下标</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">sequentialSearch</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">for</span> (<span class="keyword">int</span> i = <span class="number">0</span>; i &lt; a.length; i++) &#123;</span><br><span class="line">            <span class="keyword">if</span> (a[i] == key)</span><br><span class="line">                <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 有哨兵顺序查找</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组(下标为0存放哨兵元素)</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key 待查询关键字</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 关键字下标 返回0 则未找到</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">sequentialSearch2</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> index = a.length - <span class="number">1</span>;</span><br><span class="line">        a[<span class="number">0</span>] = key;<span class="comment">// 将下标为0的数组元素设置为哨兵</span></span><br><span class="line">        <span class="keyword">while</span> (a[index] != key) &#123;</span><br><span class="line">            index--;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> index;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 折半查找</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key 待查找关键字</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 返回折半下标， -1表示不存在该关键字</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line"></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">binarySearch</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> low, mid, high;</span><br><span class="line">        low = <span class="number">0</span>;<span class="comment">// 最小下标</span></span><br><span class="line">        high = a.length - <span class="number">1</span>;<span class="comment">// 最大小标</span></span><br><span class="line">        <span class="keyword">while</span> (low &lt;= high) &#123;</span><br><span class="line">            mid = (high + low) / <span class="number">2</span>;<span class="comment">// 折半下标</span></span><br><span class="line">            <span class="keyword">if</span> (key &gt; a[mid]) &#123;</span><br><span class="line">                low = mid + <span class="number">1</span>; <span class="comment">// 关键字比 折半值 大，则最小下标 调成 折半下标的下一位</span></span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (key &lt; a[mid]) &#123;</span><br><span class="line">                high = mid - <span class="number">1</span>;<span class="comment">// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位</span></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">return</span> mid; <span class="comment">// 当 key == a[mid] 返回 折半下标</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">/**</span></span><br><span class="line"><span class="comment">     * 插值查找</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> a 数组</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@param</span> key 待查找关键字</span></span><br><span class="line"><span class="comment">     * <span class="doctag">@return</span> 返回折半下标， -1表示不存在该关键字</span></span><br><span class="line"><span class="comment">     */</span></span><br><span class="line">    <span class="function"><span class="keyword">public</span> <span class="keyword">static</span> <span class="keyword">int</span> <span class="title">interpolationSearch</span><span class="params">(<span class="keyword">int</span>[] a, <span class="keyword">int</span> key)</span> </span>&#123;</span><br><span class="line">        <span class="keyword">int</span> low, mid, high;</span><br><span class="line">        low = <span class="number">0</span>;<span class="comment">// 最小下标</span></span><br><span class="line">        high = a.length - <span class="number">1</span>;<span class="comment">// 最大小标</span></span><br><span class="line">        <span class="keyword">while</span> (low &lt; high) &#123;</span><br><span class="line">            mid = low + (high - low) * (key - a[low]) / (a[high] - a[low]);</span><br><span class="line">            <span class="comment">// mid = (high + low) / 2;// 折半下标</span></span><br><span class="line">            <span class="keyword">if</span> (key &gt; a[mid]) &#123;</span><br><span class="line">                low = mid + <span class="number">1</span>; <span class="comment">// 关键字比 折半值 大，则最小下标 调成 折半下标的下一位</span></span><br><span class="line">            &#125; <span class="keyword">else</span> <span class="keyword">if</span> (key &lt; a[mid]) &#123;</span><br><span class="line">                high = mid - <span class="number">1</span>;<span class="comment">// 关键字比 折半值 小，则最大下标 调成 折半下标的前一位</span></span><br><span class="line">            &#125; <span class="keyword">else</span> &#123;</span><br><span class="line">                <span class="keyword">return</span> mid; <span class="comment">// 当 key == a[mid] 返回 折半下标</span></span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">return</span> -<span class="number">1</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<p><strong>四、实验任务</strong></p>
<p>认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。</p>
<p><strong>1.已知含有10个整数的查找表如下：（9，13，15，7，45，32，56，89，60，36），从键盘上输入一个整数，用顺序查找的方法在查找表中查找该整数。若存在，输出该元素的下标值，否则，给出相应的信息。</strong></p>
<p><strong>2.对有序数据表(5，7，9，12，15，18，20，22，25，30，100)，编写程序按折半查找方法查找12和28。</strong></p>
<h2 id="实验八、排序算法的实"><a href="#实验八、排序算法的实" class="headerlink" title="实验八、排序算法的实"></a>实验八、排序算法的实</h2><h2 id="一、实验目的-3"><a href="#一、实验目的-3" class="headerlink" title="一、实验目的"></a><strong>一、实验目的</strong></h2><ol>
<li>掌握常用的排序方法，并掌握用高级语言实现排序算法的方法；</li>
<li>深刻理解排序的定义和各种排序方法的特点，并能加以灵活应用；</li>
<li>了解各种方法的排序过程及其时间复杂度的分析方法。</li>
</ol>
<h2 id="二、实验要求-3"><a href="#二、实验要求-3" class="headerlink" title="二、实验要求"></a><strong>二、实验要求</strong></h2><p>统计成绩：给出n个学生的考试成绩表，每条信息由姓名和分数组成，试设计一个算法：</p>
<p>（1） 按分数高低次序，打印出每个学生在考试中获得的名次，分数相同的为同一名次；</p>
<p>（2） 按名次列出每个学生的姓名与分数。</p>
<h2 id="三、实验步骤"><a href="#三、实验步骤" class="headerlink" title="三、实验步骤"></a><strong>三、实验步骤</strong></h2><h3 id="1-定义结构体。"><a href="#1-定义结构体。" class="headerlink" title="1.定义结构体。"></a>1.定义结构体。</h3><figure class="highlight csharp"><table><tr><td class="code"><pre><span class="line">typedef  <span class="keyword">struct</span>  student&#123; </span><br><span class="line">	<span class="built_in">char</span>  name[<span class="number">8</span>];</span><br><span class="line">	<span class="built_in">int</span>  score; </span><br><span class="line">&#125;studentImform,*studentPtr；</span><br><span class="line">typedef <span class="keyword">struct</span> student&#123;</span><br><span class="line">    <span class="built_in">char</span> name[<span class="number">8</span>];</span><br><span class="line">    <span class="built_in">int</span> score;</span><br><span class="line">&#125;studentImform,*studentPtr;</span><br></pre></td></tr></table></figure>

<h3 id="2-定义结构体数组。"><a href="#2-定义结构体数组。" class="headerlink" title="2.定义结构体数组。"></a>2.定义结构体数组。</h3><figure class="highlight csharp"><table><tr><td class="code"><pre><span class="line"><span class="comment">//直接数组</span></span><br><span class="line"><span class="keyword">struct</span> student students[MAX_SIZE];</span><br><span class="line">studentImform students[MAX_SIZE];</span><br><span class="line"><span class="comment">//malloc 分配</span></span><br><span class="line">studentPtr students = (studentPtr)malloc(<span class="keyword">sizeof</span>(studentImform));</span><br><span class="line">studentPtr students = (studentPtr)malloc(MAX_SIZE*<span class="keyword">sizeof</span>(studentImform));</span><br><span class="line"><span class="comment">//直接数组</span></span><br><span class="line"><span class="keyword">struct</span> student Students[MAX_SIZE];</span><br><span class="line">studentImform Students[MAX_SIZE];</span><br><span class="line">studentImform Students[N];<span class="comment">//N确定后c89\\99标准中不支持</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//动态分配</span></span><br><span class="line">studentPtr Students = (studentPtr)malloc(<span class="keyword">sizeof</span>(studentImform));</span><br><span class="line">studentPtr Students = (studentPtr)malloc(<span class="keyword">sizeof</span>(studentImform)*MAX_SIZE);</span><br><span class="line">studentPtr Students = (studentPtr)malloc(<span class="keyword">sizeof</span>(studentImform)*N);<span class="comment">//N确定后</span></span><br></pre></td></tr></table></figure>

<h3 id="3-编写主程序，对数据进行排序。"><a href="#3-编写主程序，对数据进行排序。" class="headerlink" title="3.编写主程序，对数据进行排序。"></a>3.编写主程序，对数据进行排序。</h3><h3 id="4-要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。"><a href="#4-要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。" class="headerlink" title="4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。"></a>4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。</h3><p>4.1直接插入排序基本思想</p>
<p>排序过程：默认初始数组下标为0的数字为有序序列，每次从后续数组中顺序拿一个数字，将这个数字放到前面的有序序列中，放的位置要确保放完之后依旧是有序的。</p>
<p>将n个元素的数列分为已有序和无序两个部分，</p>
<p>插入排序过程示例如下所示：</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line">a1，a2，a3，a4，…，an</span><br><span class="line"></span><br><span class="line">a1，a2，a3，a4，…，an</span><br><span class="line"></span><br><span class="line">a1⑴，a2⑴，a3⑴，a4⑴…，an⑴</span><br><span class="line"></span><br><span class="line">a1⑴，a2⑴，a3⑴，a4⑴…，an⑴</span><br><span class="line"></span><br><span class="line">…</span><br><span class="line"></span><br><span class="line">…</span><br><span class="line"></span><br><span class="line">a1(n−<span class="number">1</span>），a2(n−<span class="number">1</span>)，…,an(n−<span class="number">1</span>)</span><br><span class="line"></span><br><span class="line">a1(n−<span class="number">1</span>），a2(n−<span class="number">1</span>)，…,an(n−<span class="number">1</span>)</span><br></pre></td></tr></table></figure>

<p>每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较，找出插入位置，将该元素插入到有序数列的合适位置中。</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insertionSort</span><span class="params">(<span class="keyword">int</span> *number,<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,ii=<span class="number">0</span>,temp=<span class="number">0</span>;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;n;i++)  <span class="comment">//循环遍历</span></span><br><span class="line">    &#123;</span><br><span class="line">        temp=number[i];  <span class="comment">//将temp每一次赋值为number[i]</span></span><br><span class="line">        ii=i<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">while</span>(ii&gt;=<span class="number">0</span> &amp;&amp; temp&gt;number[ii])   <span class="comment">//这里改顺序 (temp后的)&quot;&lt;&quot;为小到大，&quot;&gt;&quot;为大到小</span></span><br><span class="line">        &#123;</span><br><span class="line">            number[ii+<span class="number">1</span>]=number[ii];    <span class="comment">//将大的元素往前放</span></span><br><span class="line">            ii--;</span><br><span class="line">        &#125;</span><br><span class="line">        number[ii+<span class="number">1</span>]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>

<p>4.2 快速排序基本思想</p>
<p>基本思想：是对冒泡排序的一种改进。<a target="_blank" rel="noopener" href="https://blog.csdn.net/sty20030818/article/details/81272174#fn:1">1</a>快速排序由C. A. R. Hoare在1962年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。</p>
<p>排序过程：对r[s……t]中记录进行一趟快速排序，附设两个指针i和j，设rp=r[s]，x=rp.key。初始时令i=s,j=t。首先从j所指位置向前搜索第一个关键字小于x的记录，并和rp交换。再从i所指位置起向后搜索，找到第一个关键字大于x的记录，和rp交换。重复上述两步，直至i=j为止。再分别对两个子序列进行快速排序，直到每个子序列只含有一个记录为止。</p>
<p><strong>排序演示示例</strong></p>
<p>假设用户输入了如下数组：</p>
<p><a target="_blank" rel="noopener" href="https://www.notion.so/62d86bf32d3b47adb93f0d100d2a7cbc">Untitled</a></p>
<p>创建变量 i=0 （指向第一个数据）,j=5(指向最后一个数据), k=6(赋值为第一个数据的值)。</p>
<p>我们要把所有比k小的数移动到k的左面，所以我们可以开始寻找比6小的数，从j开始，从右往左找，不断递减变量j的值，我们找到第一个下标3的数据比6小，于是把数据3移到下标0的位置，把下标0的数据6移到下标3，完成第一次比较：</p>
<p><a target="_blank" rel="noopener" href="https://www.notion.so/d9f02f61ec7e47d5bad7ce2e57ab1e05">Untitled</a></p>
<p>i=0 , j=3 , k=6</p>
<p>接着，开始第二次比较，这次要变成找比k大的了，而且要从前往后找了。递加变量i，发现下标2的数据是第一个比k大的，于是用下标2的数据7和j指向的下标3的数据的6做交换，数据状态变成下表：</p>
<p><a target="_blank" rel="noopener" href="https://www.notion.so/065ba763324e41c69e1030aeba7e487e">Untitled</a></p>
<p>i=2 , j=3 ,k=6</p>
<p>称上面两次比较为一个循环。</p>
<p>接着，再递减变量jj，不断重复进行上面的循环比较。</p>
<p>在本例中，我们进行一次循环，就发现ii和jj “碰头”了：他们都指向了下标22。于是，第一遍比较结束。得到结果如下，凡是k(=6)k(=6)左边的数都比它小，凡是kk右边的数都比它大：</p>
<p><a target="_blank" rel="noopener" href="https://www.notion.so/e09113924eb34fd8aa516cd5e08cdc14">Untitled</a></p>
<p>如果ii和jj没有碰头的话，就递加i找大的，还没有，就再递减j找小的，如此反复，不断循环。注意判断和寻找是同时进行的。</p>
<p>然后，对k两边的数据，再分组分别进行上述的过程，直到不能再分组为止。</p>
<p>注意：第一遍快速排序不会直接得到最终结果，只会把比kk大和比kk小的数分到kk的两边。为了得到最后结果，需要再次对下标两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quickSortIn</span><span class="params">(<span class="keyword">int</span> left,<span class="keyword">int</span> right,<span class="keyword">int</span> a[])</span></span>;</span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span>(left&gt;=right)  <span class="comment">//如果左边索引大于或者等于右边的索引就代表已经整理完成一个组了</span></span><br><span class="line">        <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">int</span> i=left;     <span class="comment">//将区间记录下来 </span></span><br><span class="line">    <span class="keyword">int</span> j=right;</span><br><span class="line">    <span class="keyword">int</span> key=a[i];    <span class="comment">//记录参考值 </span></span><br><span class="line">    <span class="keyword">while</span>(i&lt;j)   <span class="comment">//控制在当组内寻找一遍</span></span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">while</span>(i&lt;j&amp;&amp;key&lt;=a[j])   <span class="comment">//而寻找结束的条件就是，1，找到一个小于或者大于key的数（大于或小于取决于你想升序还是降序）2，没有符合条件1的，并且i与j的大小没有反转 </span></span><br><span class="line">            j--;    <span class="comment">//向前寻找</span></span><br><span class="line">        a[i]=a[j];     <span class="comment">//找到一个这样的数后就把它赋给前面的被拿走的i的值（如果第一次循环且key是a[left]，那么就是给key）</span></span><br><span class="line">        <span class="keyword">while</span>(i&lt;j&amp;&amp;key&gt;=a[i])   <span class="comment">//这是i在当组内向前寻找，同上，不过注意与key的大小关系停止循环和上面相反，因为排序思想是把数往两边扔，所以左右两边的数大小与key的关系相反</span></span><br><span class="line">            i++;</span><br><span class="line">        a[j]=a[i];</span><br><span class="line">    &#125;</span><br><span class="line">    a[i]=key;                  <span class="comment">//当在当组内找完一遍以后就把中间数key回归</span></span><br><span class="line">    quickSortIn(left,i<span class="number">-1</span>,a);     <span class="comment">//最后用同样的方式对分出来的左边的小组进行同上的做法</span></span><br><span class="line">    quickSortIn(i+<span class="number">1</span>,right,a);    <span class="comment">//用同样的方式对分出来的右边的小组进行同上的做法</span></span><br><span class="line">                               <span class="comment">//当然最后可能会出现很多分左右，直到每一组的i = j 为止</span></span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quickSort</span><span class="params">(<span class="keyword">int</span> a[],<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">	quickSortIn(<span class="number">0</span>,n,<span class="keyword">int</span> a[]);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="4-3-选择排序"><a href="#4-3-选择排序" class="headerlink" title="4.3 选择排序"></a>4.3 选择排序</h3><p>是一种简单直观的排序算法。1它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">selectSort</span><span class="params">(<span class="keyword">int</span> R[],<span class="keyword">int</span> n)</span>    <span class="comment">//定义选择排序函数&quot;select_sort&quot;</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i, j, k, index;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; n - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        k = i;</span><br><span class="line">        <span class="keyword">for</span> (j = i + <span class="number">1</span>; j &lt; n; j++)    <span class="comment">//j初始不为0，冒泡初始为0，所以选排比冒泡快，但不稳定</span></span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (R[j] &gt; R[k])   <span class="comment">//顺序从这里改顺序 小到大&quot;&lt;&quot;,大到小&quot;&gt;&quot;</span></span><br><span class="line">                k = j;      <span class="comment">//这里是区分冒泡排序与选择排序的地方，冒泡没这句</span></span><br><span class="line">        &#125;</span><br><span class="line">        index = R[i];   <span class="comment">//交换R[i]与R[k]中的数</span></span><br><span class="line">        R[i] = R[k];    <span class="comment">//简单的交换c=a,a=b,b=c</span></span><br><span class="line">        R[k] = index;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h3 id="4-4冒泡排序"><a href="#4-4冒泡排序" class="headerlink" title="4.4冒泡排序"></a>4.4冒泡排序</h3><p>它重复地走访过要排序的元素列，一次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素已经排序完成。这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。</p>
<p>冒泡排序算法的原理如下：</p>
<p>1.比较相邻的元素。如果第一个比第二个大，就交换他们两个，这样是从小到大排。</p>
<p>(如果第一个比第二个小，交换 , 那就是从大到小排)</p>
<p>2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。</p>
<p>3.针对所有的元素重复以上的步骤，除了最后一个。</p>
<p>4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。</p>
<figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">bubbleSort</span><span class="params">(<span class="keyword">int</span> a[], <span class="keyword">int</span> n)</span>    <span class="comment">//下面是函数bubble_sort的程序 </span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i,j,temp;    <span class="comment">//定义三个整型变量 </span></span><br><span class="line">    <span class="keyword">for</span> (j=<span class="number">0</span>;j&lt;n<span class="number">-1</span>;j++)    <span class="comment">//用一个嵌套循环来遍历一遍每一对相邻元素 （所以冒泡函数慢嘛，时间复杂度高）  </span></span><br><span class="line">    &#123;                           </span><br><span class="line">        <span class="keyword">for</span> (i=<span class="number">0</span>;i&lt;n<span class="number">-1</span>-j;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i]&gt;a[i+<span class="number">1</span>])  <span class="comment">//从大到小排就把左边的&quot;&gt;&quot;改为&quot;&lt;&quot; ！！！</span></span><br><span class="line">            &#123;</span><br><span class="line">                temp=a[i];      <span class="comment">//a[i]与a[i+1](即a[i]后面那个) 交换</span></span><br><span class="line">                a[i]=a[i+<span class="number">1</span>];    <span class="comment">//基本的交换原理&quot;c=a;a=b;b=c&quot; </span></span><br><span class="line">                a[i+<span class="number">1</span>]=temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;    </span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="完整源代码"><a href="#完整源代码" class="headerlink" title="完整源代码"></a>完整源代码</h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">include</span> <span class="meta-string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"></span><br><span class="line"><span class="comment">//学生最大输入量</span></span><br><span class="line"><span class="meta">#<span class="meta-keyword">define</span> MAX_SIZE 100</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//学生信息结构体</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">student</span>&#123;</span></span><br><span class="line">    <span class="keyword">char</span> name[<span class="number">8</span>];</span><br><span class="line">    <span class="keyword">int</span> score;</span><br><span class="line">&#125;studentImform,*studentPtr;</span><br><span class="line"></span><br><span class="line"><span class="comment">//插入排序</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">insertionSort</span><span class="params">(studentPtr number,<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i=<span class="number">0</span>,ii=<span class="number">0</span>;</span><br><span class="line">    studentImform temp;</span><br><span class="line">    <span class="keyword">for</span>(i=<span class="number">1</span>;i&lt;n;i++)</span><br><span class="line">    &#123;</span><br><span class="line">        temp = number[i];</span><br><span class="line">        ii=i<span class="number">-1</span>;</span><br><span class="line">        <span class="keyword">while</span>(ii&gt;=<span class="number">0</span> &amp;&amp; temp.score &gt;number[ii].score)</span><br><span class="line">        &#123;</span><br><span class="line">            number[ii+<span class="number">1</span>]=number[ii];</span><br><span class="line">            ii--;</span><br><span class="line">        &#125;</span><br><span class="line">        number[ii+<span class="number">1</span>]=temp;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">bubbleSort</span><span class="params">(studentPtr a, <span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i,j;</span><br><span class="line">    studentImform temp;</span><br><span class="line">    <span class="keyword">for</span> (j=<span class="number">0</span>;j&lt;n<span class="number">-1</span>;j++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">for</span> (i=<span class="number">0</span>;i&lt;n<span class="number">-1</span>-j;i++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span>(a[i].score &lt; a[i+<span class="number">1</span>].score)</span><br><span class="line">            &#123;</span><br><span class="line">                temp = a[i];</span><br><span class="line">                a[i] = a[i+<span class="number">1</span>];</span><br><span class="line">                a[i+<span class="number">1</span>] = temp;</span><br><span class="line">            &#125;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//选择排序法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">selectSort</span><span class="params">(studentPtr R,<span class="keyword">int</span> n)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">int</span> i, j, k;</span><br><span class="line">    studentImform index;</span><br><span class="line">    <span class="keyword">for</span> (i = <span class="number">0</span>; i &lt; n - <span class="number">1</span>; i++) &#123;</span><br><span class="line">        k = i;</span><br><span class="line">        <span class="keyword">for</span> (j = i + <span class="number">1</span>; j &lt; n; j++)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">if</span> (R[j].score &gt; R[k].score)</span><br><span class="line">                k = j;</span><br><span class="line">        &#125;</span><br><span class="line">        index = R[i];</span><br><span class="line">        R[i] = R[k];</span><br><span class="line">        R[k] = index;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="comment">//快速排序法</span></span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quicksortIn</span><span class="params">(<span class="keyword">int</span> left,<span class="keyword">int</span> right,studentPtr a)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span>(left &gt;= right) <span class="keyword">return</span> ;</span><br><span class="line">    <span class="keyword">int</span> i=left;</span><br><span class="line">    <span class="keyword">int</span> j=right;</span><br><span class="line"></span><br><span class="line">    studentImform key=a[i];</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span>(i&lt;j)</span><br><span class="line">    &#123;</span><br><span class="line">    <span class="keyword">while</span>(i&lt;j &amp;&amp; key.score &gt;= a[j].score)</span><br><span class="line">        j--;</span><br><span class="line">        a[i]=a[j];</span><br><span class="line">    <span class="keyword">while</span>(i&lt;j &amp;&amp; key.score &lt;= a[i].score)</span><br><span class="line">        i++;</span><br><span class="line">        a[j]=a[i];</span><br><span class="line">    &#125;</span><br><span class="line">    a[i] = key;</span><br><span class="line">    quicksortIn(left,i<span class="number">-1</span>,a);</span><br><span class="line">    quicksortIn(i+<span class="number">1</span>,right,a);</span><br><span class="line">    &#125;</span><br><span class="line"><span class="function"><span class="keyword">void</span> <span class="title">quickSort</span><span class="params">(studentPtr a,<span class="keyword">int</span> n)</span></span>&#123;</span><br><span class="line">    quicksortIn(<span class="number">0</span>,n+<span class="number">1</span>,a);</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="keyword">int</span> <span class="title">main</span><span class="params">()</span></span>&#123;</span><br><span class="line">    <span class="comment">//定义变量</span></span><br><span class="line">    <span class="keyword">int</span> N,i=<span class="number">0</span>,way;</span><br><span class="line">    studentImform Students[MAX_SIZE] = &#123;<span class="number">0</span>&#125;;</span><br><span class="line">    <span class="comment">//输入信息</span></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请输入学生数量\\n&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;N);</span><br><span class="line"></span><br><span class="line">    <span class="keyword">while</span> (N&lt;=<span class="number">0</span>)&#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;输入不合法，请重新输入\\n&quot;</span>);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;N);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请依次输入%d学生的姓名及成绩\\n&quot;</span>,N);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j= <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,Students[j].name);</span><br><span class="line">        <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;Students[j].score);</span><br><span class="line">        <span class="keyword">while</span> (Students[i].name == <span class="literal">NULL</span> || Students[j].score&lt;<span class="number">0</span>)&#123;</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;输入不合法，请重新输入%d位同学的信息\\n&quot;</span>,j+<span class="number">1</span>);</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%s&quot;</span>,Students[j].name);</span><br><span class="line">            <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;Students[j].score);</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;请选择排序方式:\\n1.直接插入排序\\n2.快速排序\\n3.选择排序\\n4.\\n&quot;</span>);</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;way);</span><br><span class="line">    <span class="keyword">switch</span> (way) &#123;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">1</span>:</span><br><span class="line">            insertionSort(Students,N);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">2</span>:</span><br><span class="line">            quickSort(Students,N);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">3</span>:</span><br><span class="line">            selectSort(Students,N);</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        <span class="keyword">case</span> <span class="number">4</span>:</span><br><span class="line">            bubbleSort(Students,N);</span><br><span class="line">        <span class="keyword">default</span>:</span><br><span class="line">            <span class="built_in">printf</span>(<span class="string">&quot;输入有误\\n&quot;</span>);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\\t序号  \\t姓名\\t:  \\t分数\\n&quot;</span>);</span><br><span class="line">    <span class="keyword">for</span> (<span class="keyword">int</span> j = <span class="number">0</span>; j &lt; N; ++j) &#123;</span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;\\t%-d\\t%-s\\t:\\t%-d\\n&quot;</span>,j,Students[j].name,Students[j].score);</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>

<h2 id="老师标准子函数"><a href="#老师标准子函数" class="headerlink" title="老师标准子函数"></a>老师标准子函数</h2><figure class="highlight c"><table><tr><td class="code"><pre><span class="line"></span><br></pre></td></tr></table></figure>

<p><strong>四、实验任务</strong></p>
<p>认真阅读与理解实验内容的具体要求，参考教材相关章节，编写实验程序并上机调试与测试，完成实验报告的撰写。</p>
</article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="mailto:undefined">谭自财</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://tanzicai.gitee.io/2021/03/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%AE%9E%E9%AA%8C%E6%8C%87%E5%AF%BC%E4%B9%A6/">https://tanzicai.gitee.io/2021/03/21/数据结构与算法实验指导书/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://tanzicai.gitee.io" target="_blank">小谭的部落阁</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/tags/%E5%B7%A5%E5%85%B7/">工具</a><a class="post-meta__tags" href="/tags/%E8%AE%BA%E6%96%87/">论文</a><a class="post-meta__tags" href="/tags/%E5%85%AC%E5%BC%8F/">公式</a><a class="post-meta__tags" href="/tags/latex/">latex</a></div><div class="post_share"><div class="social-share" data-image="/img/survivors_v02_5120x2880.png" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/social-share.js/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/social-share.js/dist/js/social-share.min.js" defer></script></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/2021/03/21/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84-C%E8%AF%AD%E8%A8%80-%E7%AC%94%E8%AE%B0/"><img class="prev-cover" src="/img/CSMS.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">数据结构(C语言)笔记</div></div></a></div><div class="next-post pull-right"><a href="/2021/03/21/Tex%E8%A1%8C%E5%86%85%E5%85%AC%E5%BC%8F%E8%AF%B4%E6%98%8E/"><img class="next-cover" src="/img/GRSS.png" onerror="onerror=null;src='/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Tex行内公式说明</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span> 相关推荐</span></div><div class="relatedPosts-list"><div><a href="/2021/03/21/Tex行内公式说明/" title="Tex行内公式说明"><img class="cover" src="/img/GRSS.png" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2021-03-21</div><div class="title">Tex行内公式说明</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="card-widget card-info"><div class="card-info-avatar is-center"><img class="avatar-img" src="https://gitee.com/tanzicai/drawingbed/raw/master/img/20210609205810.png" onerror="this.onerror=null;this.src='/img/friend_404.gif'" alt="avatar"/><div class="author-info__name">谭自财</div><div class="author-info__description">你别卷入世俗，我别沉迷初遇</div></div><div class="card-info-data"><div class="card-info-data-item is-center"><a href="/archives/"><div class="headline">文章</div><div class="length-num">35</div></a></div><div class="card-info-data-item is-center"><a href="/tags/"><div class="headline">标签</div><div class="length-num">50</div></a></div><div class="card-info-data-item is-center"><a href="/categories/"><div class="headline">分类</div><div class="length-num">12</div></a></div></div><a class="button--animated" id="card-info-btn" target="_blank" rel="noopener" href="https://github.com/tanzicai"><i class="fab fa-github"></i><span>Follow Me</span></a><div class="card-info-social-icons is-center"><a class="social-icon" href="https://github.com/tanzicai" target="_blank" title="Github"><i class="fab fa-github"></i></a><a class="social-icon" href="https://gitee.com/tanzicai" target="_blank" title="Github"><i class="fab fa-git-square"></i></a><a class="social-icon" href="http://wpa.qq.com/msgrd?v=3&amp;uin=1728561744&amp;site=qq&amp;menu=yes" target="_blank" title="QQ"><i class="fas fa-qq"></i></a><a class="social-icon" href="mailto:1728561744@qq.com" target="_blank" title="Email"><i class="fas fa-envelope"></i></a></div></div><div class="card-widget card-announcement"><div class="item-headline"><i class="fas fa-bullhorn card-announcement-animation"></i><span>公告</span></div><div class="announcement_content">本站正在切换主题测试，如有错误提示，请联系我，谢谢</div></div><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E3%80%8A%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E3%80%8B%E4%B8%8A%E6%9C%BA%E5%AE%9E%E9%AA%8C%E5%86%85%E5%AE%B9%E5%92%8C%E8%A6%81%E6%B1%82"><span class="toc-number">1.</span> <span class="toc-text">《数据结构》上机实验内容和要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E6%8A%A5%E5%91%8A%E8%A6%81%E6%B1%82"><span class="toc-number">2.</span> <span class="toc-text">实验报告要求</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%F0%9F%91%A6%E5%AE%9E%E9%AA%8C%E4%B8%80%E3%80%81%E9%A1%BA%E5%BA%8F%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number"></span> <span class="toc-text">👦实验一、顺序表的实现及应用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84"><span class="toc-number">1.</span> <span class="toc-text">一、实验目的</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82"><span class="toc-number">2.</span> <span class="toc-text">二、实验要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E7%A8%8B%E5%BA%8F%E4%BB%A3%E7%A0%81"><span class="toc-number">3.</span> <span class="toc-text">三、程序代码</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E5%90%88%E5%B9%B6%E5%87%BD%E6%95%B0-WriteByLiyihan"><span class="toc-number">3.1.</span> <span class="toc-text">合并函数_WriteByLiyihan</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%9B%E3%80%81%E5%AE%9E%E9%AA%8C%E4%BB%BB%E5%8A%A1"><span class="toc-number">4.</span> <span class="toc-text">四、实验任务</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E4%BA%8C-%E9%93%BE%E8%A1%A8%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number"></span> <span class="toc-text">实验二 链表的实现及应用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84-1"><span class="toc-number">1.</span> <span class="toc-text">一、实验目的</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82-1"><span class="toc-number">2.</span> <span class="toc-text">二、实验要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E7%A8%8B%E5%BA%8F%E4%BB%A3%E7%A0%81%EF%BC%9A"><span class="toc-number">3.</span> <span class="toc-text">三、程序代码：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E5%AE%9E%E9%AA%8C%E4%BB%BB%E5%8A%A1"><span class="toc-number">4.</span> <span class="toc-text">三、实验任务</span></a></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E4%B8%89%E3%80%81%E6%A0%88%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number"></span> <span class="toc-text">实验三、栈的实现及应用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84-2"><span class="toc-number">1.</span> <span class="toc-text">一、实验目的</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82-2"><span class="toc-number">2.</span> <span class="toc-text">二、实验要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E8%A7%A3%E9%A2%98%E5%8F%82%E8%80%83%E6%80%9D%E8%B7%AF"><span class="toc-number">3.</span> <span class="toc-text">三、解题参考思路</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%9B%E3%80%81%E5%AE%9E%E9%AA%8C%E4%BB%BB%E5%8A%A1-1"><span class="toc-number">4.</span> <span class="toc-text">四、实验任务</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%94%E3%80%81%E5%AE%9E%E9%AA%8C%E6%80%9D%E8%B7%AF"><span class="toc-number">5.</span> <span class="toc-text">五、实验思路</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%88%E7%9A%84%E5%AE%9A%E4%B9%89"><span class="toc-number">5.1.</span> <span class="toc-text">栈的定义</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E6%A0%88%E7%9A%84%E6%93%8D%E4%BD%9C"><span class="toc-number">5.2.</span> <span class="toc-text">栈的操作</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E7%AC%A6%E5%8F%B7%E4%BC%98%E5%85%88%E7%BA%A7%E5%88%A4%E6%96%AD%E5%87%BD%E6%95%B0"><span class="toc-number">5.3.</span> <span class="toc-text">符号优先级判断函数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BB%E5%87%BD%E6%95%B0%E6%80%9D%E8%B7%AF1"><span class="toc-number">5.4.</span> <span class="toc-text">主函数思路1</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%BB%E5%87%BD%E6%95%B0%E6%80%9D%E8%B7%AF2%EF%BC%9A%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E6%8C%87%E5%AF%BC%E4%B9%A6%E8%A6%81%E6%B1%82"><span class="toc-number">5.5.</span> <span class="toc-text">主函数思路2：数据结构指导书要求</span></a></li></ol></li></ol></li><li class="toc-item toc-level-1"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E5%9B%9B%E3%80%81%E9%98%9F%E5%88%97%E7%9A%84%E5%AE%9E%E7%8E%B0%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number"></span> <span class="toc-text">实验四、队列的实现及应用</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E8%A7%A3%E9%A2%98%E5%8F%82%E8%80%83%E6%80%9D%E8%B7%AF-1"><span class="toc-number">1.</span> <span class="toc-text">三、解题参考思路</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E6%95%B0%E6%8D%AE%E6%8F%8F%E8%BF%B0%EF%BC%88%E7%BB%93%E6%9E%84%E4%BD%93%E5%AE%9A%E4%B9%89%EF%BC%89"><span class="toc-number">1.1.</span> <span class="toc-text">一、数据描述（结构体定义）</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E5%AD%98%E5%8F%96%E6%93%8D%E4%BD%9C%EF%BC%88%E9%98%9F%E5%88%97%E6%93%8D%E4%BD%9C%E5%87%BD%E6%95%B0%EF%BC%89"><span class="toc-number">1.2.</span> <span class="toc-text">二、存取操作（队列操作函数）</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E4%B8%BB%E5%87%BD%E6%95%B0%E6%B5%81%E7%A8%8B"><span class="toc-number">2.</span> <span class="toc-text">三、主函数流程</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%9B%9B%E3%80%81%E5%AE%9E%E9%AA%8C%E4%BB%BB%E5%8A%A1-2"><span class="toc-number">3.</span> <span class="toc-text">四、实验任务</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%94%E3%80%81%E6%B3%A8%E6%84%8F%E7%82%B9"><span class="toc-number">4.</span> <span class="toc-text">五、注意点</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E4%BA%94%E3%80%81%E4%BA%8C%E5%8F%89%E6%A0%91%E6%93%8D%E4%BD%9C%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number">5.</span> <span class="toc-text">实验五、二叉树操作及应用</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E3%80%81-%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84"><span class="toc-number">6.</span> <span class="toc-text">一、 实验目的</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E7%9B%B8%E5%85%B3%E7%9F%A5%E8%AF%86"><span class="toc-number">7.</span> <span class="toc-text">二、相关知识</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#%E9%81%8D%E5%8E%86"><span class="toc-number">7.1.</span> <span class="toc-text">遍历</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81-%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82"><span class="toc-number">8.</span> <span class="toc-text">二、 实验要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81-%E5%AE%9E%E9%AA%8C%E4%BB%BB%E5%8A%A1%EF%BC%9A"><span class="toc-number">9.</span> <span class="toc-text">三、 实验任务：</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E5%85%AD%E3%80%81%E5%9B%BE%E7%9A%84%E9%81%8D%E5%8E%86%E6%93%8D%E4%BD%9C%E5%8F%8A%E5%BA%94%E7%94%A8"><span class="toc-number">10.</span> <span class="toc-text">实验六、图的遍历操作及应用</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E4%B8%83%E3%80%81%E6%9F%A5%E6%89%BE%E7%AE%97%E6%B3%95%E7%9A%84%E5%AE%9E%E7%8E%B0"><span class="toc-number">11.</span> <span class="toc-text">实验七、查找算法的实现</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#C%E6%96%B9%E5%BC%8F%E5%AE%9E%E7%8E%B0"><span class="toc-number">11.1.</span> <span class="toc-text">C方式实现</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#Java%E6%96%B9%E6%B3%95%E5%AE%9E%E7%8E%B0"><span class="toc-number">11.2.</span> <span class="toc-text">Java方法实现</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%9E%E9%AA%8C%E5%85%AB%E3%80%81%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84%E5%AE%9E"><span class="toc-number">12.</span> <span class="toc-text">实验八、排序算法的实</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%80%E3%80%81%E5%AE%9E%E9%AA%8C%E7%9B%AE%E7%9A%84-3"><span class="toc-number">13.</span> <span class="toc-text">一、实验目的</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%BA%8C%E3%80%81%E5%AE%9E%E9%AA%8C%E8%A6%81%E6%B1%82-3"><span class="toc-number">14.</span> <span class="toc-text">二、实验要求</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E4%B8%89%E3%80%81%E5%AE%9E%E9%AA%8C%E6%AD%A5%E9%AA%A4"><span class="toc-number">15.</span> <span class="toc-text">三、实验步骤</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-%E5%AE%9A%E4%B9%89%E7%BB%93%E6%9E%84%E4%BD%93%E3%80%82"><span class="toc-number">15.1.</span> <span class="toc-text">1.定义结构体。</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-%E5%AE%9A%E4%B9%89%E7%BB%93%E6%9E%84%E4%BD%93%E6%95%B0%E7%BB%84%E3%80%82"><span class="toc-number">15.2.</span> <span class="toc-text">2.定义结构体数组。</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-%E7%BC%96%E5%86%99%E4%B8%BB%E7%A8%8B%E5%BA%8F%EF%BC%8C%E5%AF%B9%E6%95%B0%E6%8D%AE%E8%BF%9B%E8%A1%8C%E6%8E%92%E5%BA%8F%E3%80%82"><span class="toc-number">15.3.</span> <span class="toc-text">3.编写主程序，对数据进行排序。</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-%E8%A6%81%E6%B1%82%E8%87%B3%E5%B0%91%E9%87%87%E7%94%A8%E4%B8%A4%E7%A7%8D%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E5%AE%9E%E7%8E%B0%EF%BC%8C%E5%A6%82%E7%9B%B4%E6%8E%A5%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F%E3%80%81%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F%E7%AD%89%E7%AE%97%E6%B3%95%E3%80%82"><span class="toc-number">15.4.</span> <span class="toc-text">4.要求至少采用两种排序算法实现，如直接插入排序、快速排序等算法。</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-3-%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F"><span class="toc-number">15.5.</span> <span class="toc-text">4.3 选择排序</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-4%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F"><span class="toc-number">15.6.</span> <span class="toc-text">4.4冒泡排序</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E5%AE%8C%E6%95%B4%E6%BA%90%E4%BB%A3%E7%A0%81"><span class="toc-number">16.</span> <span class="toc-text">完整源代码</span></a></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E8%80%81%E5%B8%88%E6%A0%87%E5%87%86%E5%AD%90%E5%87%BD%E6%95%B0"><span class="toc-number">17.</span> <span class="toc-text">老师标准子函数</span></a></li></ol></div></div><div class="card-widget card-recent-post"><div class="item-headline"><i class="fas fa-history"></i><span>最新文章</span></div><div class="aside-list"><div class="aside-list-item"><a class="thumbnail" href="/2022/02/10/%E5%B8%B8%E7%94%A8%E7%B1%BB/" title="Java常用类"><img src="https://gitee.com/tanzicai/file-pan/raw/master/img/20220209171157.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java常用类"/></a><div class="content"><a class="title" href="/2022/02/10/%E5%B8%B8%E7%94%A8%E7%B1%BB/" title="Java常用类">Java常用类</a><time datetime="2022-02-10T12:25:00.000Z" title="发表于 2022-02-10 20:25:00">2022-02-10</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/09/%E5%BC%82%E5%B8%B8/" title="Java异常"><img src="/img/survivors_v03_5120x2880.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java异常"/></a><div class="content"><a class="title" href="/2022/02/09/%E5%BC%82%E5%B8%B8/" title="Java异常">Java异常</a><time datetime="2022-02-09T13:25:00.000Z" title="发表于 2022-02-09 21:25:00">2022-02-09</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/09/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1%E7%BC%96%E7%A8%8B/" title="Java面向对象编程"><img src="/img/CTTN.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java面向对象编程"/></a><div class="content"><a class="title" href="/2022/02/09/%E9%9D%A2%E5%90%91%E5%AF%B9%E8%B1%A1%E7%BC%96%E7%A8%8B/" title="Java面向对象编程">Java面向对象编程</a><time datetime="2022-02-09T13:25:00.000Z" title="发表于 2022-02-09 21:25:00">2022-02-09</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/09/%E6%95%B0%E7%BB%84%E8%AF%A6%E8%A7%A3/" title="Java数组详解"><img src="/img/CNYN.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java数组详解"/></a><div class="content"><a class="title" href="/2022/02/09/%E6%95%B0%E7%BB%84%E8%AF%A6%E8%A7%A3/" title="Java数组详解">Java数组详解</a><time datetime="2022-02-09T13:25:00.000Z" title="发表于 2022-02-09 21:25:00">2022-02-09</time></div></div><div class="aside-list-item"><a class="thumbnail" href="/2022/02/09/%E6%96%B9%E6%B3%95%E8%AF%A6%E8%A7%A3/" title="Java方法详解"><img src="/img/WHT.png" onerror="this.onerror=null;this.src='/img/404.jpg'" alt="Java方法详解"/></a><div class="content"><a class="title" href="/2022/02/09/%E6%96%B9%E6%B3%95%E8%AF%A6%E8%A7%A3/" title="Java方法详解">Java方法详解</a><time datetime="2022-02-09T12:25:00.000Z" title="发表于 2022-02-09 20:25:00">2022-02-09</time></div></div></div></div></div></div></main><footer id="footer" style="background-image: url('/img/survivors_v02_5120x2880.png')"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2022 By 谭自财</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div><div class="footer_custom_text">欢迎进入 <a href="https://tanzicai.gitee.io">小谭的部落阁</a>!</div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="font-plus" type="button" title="放大字体"><i class="fas fa-plus"></i></button><button id="font-minus" type="button" title="缩小字体"><i class="fas fa-minus"></i></button><button id="translateLink" type="button" title="简繁转换">繁</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/js/utils.js"></script><script src="/js/main.js"></script><script src="/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/instant.page/instantpage.min.js" type="module"></script><script>var preloader = {
  endLoading: () => {
    document.body.style.overflow = 'auto';
    document.getElementById('loading-box').classList.add("loaded")
  },
  initLoading: () => {
    document.body.style.overflow = '';
    document.getElementById('loading-box').classList.remove("loaded")

  }
}
window.addEventListener('load',preloader.endLoading())</script><div class="js-pjax"></div><script id="click-heart" src="https://cdn.jsdelivr.net/npm/butterfly-extsrc@1/dist/click-heart.min.js" async="async" mobile="false"></script><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>